Alexander S. Okhotin

Professor, Deputy dean

29 Line 14th (Vasilyevsky Island), 199178 Saint Petersburg, Russia

By appointment

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

- formal grammars
- complexity in automata theory
- parsing algorithms

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

Course name

Year

Semester

Role