St. Petersburg, 199178, Russia, The 14th line of the Vasilievsky Island house 29 B
(812) 363-68-71, (812) 363-68-72
ru en
Alexander S. Okhotin
Alexander S. Okhotin
Professor
Contacts:

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

alexander.okhotin@spbu.ru

http://users.math-cs.spbu.ru/~okhotin/

Reception hours:

By appointment


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

Course name
Year
Semester
Role
Course name
Year
2017–2018
Semester
I, II
Role
Lecturer, seminarian
Course name
Year
2017–2018
Semester
III, IV
Role
Lecturer
Course name
Year
2017–2018
Semester
VI
Role
Lecturer
Year
2017–2018
Semester
VI
Role
Teaching assistant