Algorithms, Logic, and Theory of Computing

Our research on algorithms and data structures includes graph algorithms, temporal networks, approximation algorithms, distributed algorithms, computational complexity, combinatorial search, and algorithms on strings. Many of the algorithmic questions we attack originate from real world problems in bioinformatics and computational biology, as well as planning and optimization in the context of medical diagnosis and market investments. We also investigate decision tree and random forests based models for deep learning applications. Regarding strings and sequences, we work on pattern matching and mining, the design and analysis of compressed data structures, as well as on combinatorics on words, text compression, grammars, and string rewriting. Members of the area work on reactive synthesis from temporal logic specifications, complexity of properties for formal languages, and decidability of the model checking/satisfiability problem for interval temporal logic. Our research also includes formal methods applied to concurrent and distributed languages, in particular, process calculi for mobile systems, concurrent and distributed object-oriented languages, formalisation of distributed algorithms, and semantics foundations and security analysis of cyber-physical systems and smart devices in the context of the Internet of Things paradigm. Further topics are the extraction of algorithms from proofs in constructive analysis, the use of minimal logic in mathematical proofs, and the study of computability models in higher order computability theory from a categorical point of view. Finally, we study models for the representation of real-time concurrent systems that include stochastic as well as hybrid behavior, as well as unconventional models of computation (often bio-inspired), molecular algorithms, and self organization processes.