Algorithms and Logic section (Algolog)

The research area of the Algorithms and Logic section is the scientific foundation for constructing robust, efficient, and intelligent software applications based on mathematically sound solutions. Two crucial aspects when designing efficient software are large data sets and intrinsically hard problems. The naive algorithm or data structure usually only suffices for solving small scale problems. A simple search engine can easily index the contents of a drive on a personal computer, but indexing the web is much more difficult. Similarly, an autonomous robot can plan its actions optimally by an exhaustive state space search only if the number of possible actions and states is very limited. Thus more advanced algorithms/methods are needed to solve these problems. In software applications for complex problems, often some degree of intelligence is needed in addition to efficiency. Intelligence means that the software is able to collect and categorize knowledge, do logical reasoning, learn from experiences, and communicate and negotiate with other software applications. The scientific foundation for such applications includes computational logic and logic-based AI.

The research of the Algorithm and Logic section covers:

• Algorithmics: Algorithmics is the part of computer science that deals with the design and analysis of algorithms and data structures and constitutes the scientific foundation for reasoning about resources used in computing such as time and space. This covers both the design and analysis of efficient algorithms solving concrete problems, and also with identifying common patterns of problems and associated algorithmic paradigms that can lead to efficient solutions for classes of problems.

The section’s research in this area includes: Approximation algorithms, stochastic search algorithms/heuristics, algorithms for statistics, data structures, and pattern matching.

• Computational Logic: Computational logic is the study of logic and logical methods within computer science. Logic is the study of valid inferences, and in computational logic it is studies how to automate such inferences on a computer. Computational logic is used for the specification and verification of software and hardware systems, for topics in databases and programming languages, and for logic-based AI, such as automated reasoning and knowledge-based systems.

The section’s research in this area includes: Modal logic, hybrid logic, temporal and interval logics for specification and verification, tableau-based logical decision procedures, higher-order logic, non-classical logic, array-based logic and systems, algorithms for proof systems, multi-agent systems, knowledge-based systems, formal ontologies, and argumentation theory using ontological semantics.

Further information: Algolog Wiki