Back to search

IS-DAAD-Forskerutveksl. Norge-Tyskland

Algorithmic Automata Theory: A multivariate approach

Awarded: NOK 37,702

Automata theory (and more generally speaking, formal languages) is one of the most traditional areas in (theoretical) computer science. Hence, this field has found applications in quite diverse areas of science, as linguistics, biology, and clearly many more applied areas of computer science, such as compiler construction, software engineering, or hardware design, to mention only a few. On the other hand, the field of multivariate algorithms deals with the development of techniques to handle computationally hard problems by finding clever ways to deal with certain properties of the inputs which are quantified by numerical parameters. In particular, the running time of algorithms developed in this framework have a polynomial dependence on the size of the input and potentially, an exponential dependence on the magnitude of the parameters. It turns out that in many situations of practical relevance, these parameters are very small. Therefore, multivariate algorithms very often perform well on instances inspired by practical applications. Currently, techniques from the theory of multivariate algorithms have been hardly applied to the study of problems in automata theory. Similarly, there are only a few examples of situations in which techniques from automata theory have been used in the development of faster multivariate algorithms. The goal of this project is to establish deep connections between these fields, by using techniques from automata theory to attack hard problems in the field of multivariate algorithms and vice versa.

Funding scheme:

IS-DAAD-Forskerutveksl. Norge-Tyskland