Alexander Okhotin

I am a Russian mathematician in the Finnish service. I have been working at the Department of Mathematics 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 of 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).

My curriculum vitae: PostScript, PDF, HTML.
My personal page (in Russian).

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.

State-of-the-art survey: “Conjunctive and Boolean grammars: the true general case of the context-free grammars” (draft). (October 2011)
Nine open problems for conjunctive and Boolean grammars (#2 solved in 2007, #3 solved in 2009).
Recently published papers: “Expressive power of LL(k) Boolean grammars” (accepted to TCS). (May 2011)
Recent new manuscripts: “Defining contexts in context-free grammars” (with M. Barash, accepted to LATA 2012). (November 2011)

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.

In preparation: a handbook chapter “Language equations” by Michal Kunc and myself. (Announced in October 2011)
Selected papers on language equations and computability: “Decision problems for language equations” (ICALP 2003; final version in JCSS), “On the computational completeness of equations over sets of natural numbers” (with Artur Jeż; ICALP 2008, full version in progress), “Equations over sets of natural numbers with addition only” (with Artur Jeż; STACS 2009, full version submitted), “On language equations XXK=XXL and XM=N over a unary alphabet” (with Tommi Lehtinen; DLT 2010, full version in progress).
“Language equations: a story of computational completeness” (slides from a Dagstuhl seminar, 2010).

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 new papers: “Describing periodicity in two-way deterministic finite automata using transformation semigroups” (with M. Kunc, presented at DLT 2011), “State complexity of operations on two-way deterministic finite automata over a unary alphabet” (with M. Kunc, presented at DCFS 2011), “State complexity of operations on input-driven pushdown automata” (with K. Salomaa, presented at MFCS 2011). (June 2011)
Recently published papers: “State complexity of union and intersection for two-way nondeterministic finite automata” (with M. Kunc, published in Fund.Inf.), “Unambiguous finite automata over a unary alphabet” (to appear in I&C).

Teaching

Formal grammars, University of Turku, Spring 2009.
Formal languages and parsing (in Russian), St. Petersburg, October 2009. (April 2010)
Formal grammars, University of Wrocław, Poland, November 2009.

Students, current and former

Dr. Artur Jeż (Ph. D. student at the University of Wrocław, Poland; supervised jointly with Krzysztof Loryś), defended on 14 September 2010, with distinction; Polish Prime Minister's Award for an Outstanding Ph. D. thesis (2011).
Tommi Lehtinen (Ph. D. student at the University of Turku since 2007).
Mikhail Barash (Ph. D. student at the University of Turku since 2011; supervised jointly with Tero Harju).

Other duties

Conference programme committees: LATA 2007, TALE 2007, SOFSEM 2008, AutoMathA 2009, DCFS 2009, MFCS 2009, FCT 2009, CIAA 2010, NCMA 2010, LATA 2011, DLT 2011, DCFS 2011, CIAA 2011, CSR 2012, CIAA 2012.

Programming

Dolphin, a lexical analyzer generator.
Whale, an LR parser generator.
Whale Calf, a parser generator for conjunctive grammars. (March 2010)

Various

Photographs from conferences:
- From CIAA 2002 conference, Tours, France, July 3–5, 2002.
- From CIAA 2004 conference, Kingston, Ontario, Canada, July 22–24, 2004.
- From AFL 2005 conference, Dobogoko, Hungary, May 17–20, 2005.
- From DCFS 2005 workshop, Como, Italy, June 30–July 2, 2005.
- From DLT 2005 (second part here) conference, Palermo, Italy, July 4–8, 2005.
- From DLT 2006 conference, Santa Barbara, USA, June 26–29, 2006.
- From Workshop on Fibonacci Words, Turku, Finland, September 27–30, 2006.
- From DLT 2007 conference, Turku, Finland, June 3–6, 2007.
Selected photographs: animals, churches, Good Friday procession (Tarragona, Spain, April 14, 2006), other subjects.

E-mail:

Last updated: January A.D. 2012.