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 Okhotin
Alexander Okhotin
Contacts:

14th Line 29B, Vasilyevsky Island, St.Petersburg, 199178, Russia

alexander.okhotin@spbu.ru

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

Reception hours:

Please, contact me in advance.


Education

10.2004 — Ph.D. (computer science)
Place of the defense: Queen's University (Kingston, Ontario, Canada)
Thesis title: Boolean grammars: expressive power and parsing algorithms
Thesis advisor: K.T. Salomaa

12.2002 — PhD (discrete mathematics and mathematical cybernetics)
Place of the defense: Lomonosov Moscow State University
Thesis title: Analysis of parsing algorithms for conjunctive grammars.
Thesis advisor: V.Zaharov

06.2001 — Specialist degree in applied mathematics
Place of the defense: Lomonosov 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. DOI: 10.1016/j.ic.2012.01.003
  2. A. Okhotin, Conjunctive and Boolean grammars: the true general case of the context-free grammars, Computer Science Review, 9 (2013), 27–59. DOI: 10.1016/j.cosrev.2013.06.001
  3. A. Jez, A. Okhotin, Computational completeness of equations over sets of natural numbers, Information and Computation, 237 (2014), 56–94. DOI: 10.1016/j.ic.2014.05.001
  4. A. Okhotin, Parsing by matrix multiplication generalized to Boolean grammars, Theoretical Computer Science, 516 (2014), 101–120. DOI: 10.1016/j.tcs.2013.09.011
  5. M. Barash, A. Okhotin, An extension of context-free grammars with one-sided context specifications, Information and Computation, 237 (2014), 268–293. DOI: 10.1016/j.ic.2014.03.003

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