Education

10.2004 — Ph.D. in Computer Science
Institution: Queen's University (Kingston, Ontario, Canada)
Thesis title: Boolean grammars: expressive power and parsing algorithms
Advisor: K.T. Salomaa

12.2002 — Ph.D. (C.Sc.) in Mathematics and Physics («Discrete Mathematics and Mathematical Cybernetics»)
Institution: Moscow State University
Thesis title: Analysis of parsing algorithms for conjunctive grammars.
Advisor: V.A. Zaharov

06.2001 — Specialist Degree in Applied Mathematics
Institution: Moscow State University

Scientific interests

• formal grammars
• complexity in automata theory
• parsing algorithms

Selected publications

1. A. Okhotin, Unambiguous finite automata over a unary alphabet, Information and Computation, 212 (2012), 15–36.
2. A. Okhotin, Conjunctive and Boolean grammars: the true general case of the context-free grammars, Computer Science Review, 9 (2013), 27–59.
3. A. Jez and A. Okhotin, Computational completeness of equations over sets of natural numbers, Information and Computation, 237 (2014), 56–94.
4. A. Okhotin, Parsing by matrix multiplication generalized to Boolean grammars, Theoretical Computer Science, 516 (2014), 101–120.
5. M. Barash and A. Okhotin, An extension of context-free grammars with one-sided context specifications, Information and Computation, 237 (2014), 268–293.

Teaching