Alexander Okhotin

I am a Russian mathematician in the Finnish service. I have been working at the Department of Mathematics and Statistics of the University of Turku, first as a research fellow of the Academy of Finland (2006–2011), and then as a researcher of the Turku Collegium for Science and Medicine (since 2012). My research interests belong to the area of formal language and automata theory, and my main subjects are formal grammars and their parsing algorithms, language equations in connection with computability, and descriptional complexity of finite automata. I received my education at Moscow State University, Russia (1996–2001), and at Queen's University, Canada (2001–2004), and got a habilitation from the University of Turku (2009).

Research on formal grammars

My research on grammars began with understanding context-free grammars as a logic for representing syntax, which prompted me to investigate the power of Boolean connectives in this logic. This outlook led me to conjunctive grammars, which allow a conjunction operation in their rules, and to Boolean grammars, which further allow the negation. My subsequent research has shown that the main practically relevant properties of context-free grammars, including most of the parsing algorithms, equally hold for Boolean grammars. These developments significantly change the perspective on formal grammars in general, and now my mission is to work out an up-to-date theory of formal grammars.

Research on language equations

Equations with formal languages as unknowns naturally arise when reasoning about sets of strings, and they have been used in many applied areas of computer science. These applications would benefit from a general theory of language equations. I have been working towards such a theory, exploring the relations between language equations and computation, and tracing the border between their decidability and undecidability. The latest findings are that, in short, almost all language equations are computationally complete, including those over a one-letter alphabet and with concatenation as the only operation.

Research on descriptional complexity of automata

It is well-known that converting a nondeterministic finite automaton (NFA) to an equivalent deterministic one (DFA) requires exponentially many states; representing a Kleene star of a DFA also leads to an exponential blowup in the size of the description. For ordinary DFAs and NFAs, all problems of this kind have long been solved. I am occasionally investigating similar problems for a few related models, such as unambiguous finite automata (UFA), two-way finite automata (2DFA, 2NFA) and input-driven pushdown automata (IDPDA).

Recent teaching

Students, current and former

Other duties

Programming

Various

E-mail: christian_name.family_name@utu.fi.

Last updated: August A.D. 2013.