(Ph. D. 2004, Queen's University)
is a professor of theoretical computer science
in the mathematics programme
of St. Petersburg State University.
His general research interests are in the area
of formal language and automata theory.
The main topics of his current research are formal grammars
and descriptional complexity of automata.
At the moment, Dr. Okhotin's main mission in his career
is to finish his book on formal grammars.
- Curriculum vitae
(the 20th of July, 2017)
- Current status of the Formal Grammars draft:
459 pages, 93 figures, 624 names in the name index. (the 20th of July, 2017)
- Refereeing queue:
9 papers under review (of them 3 overdue).
Research on formal grammars
Formal grammars are mathematical models of syntax.
Dr. Okhotin introduced and studied
two extensions of ordinary (context-free) grammars:
which allow a conjunction operation in their rules,
and Boolean grammars,
which further allow the negation.
These grammars are important for inheriting
the main practically relevant properties of ordinary grammars;
in particular, most of their parsing algorithms.
- State-of-the-art survey of conjunctive and Boolean grammars:
Conjunctive and Boolean grammars: the true general case of the context-free grammars
(Computer Science Review, 2013;
author's pre-acceptance draft).
- A talk on formal grammars in general:
Formal grammars after the Cuban missile crisis
(in English: May 2014, Umeå, Sweden,
in Russian: February 2016, Moscow, Russia).
- Nine open problems for conjunctive and Boolean grammars
(#2 solved in 2007, #3 solved in 2009).
- Recent new manuscripts:
Conjunctive categorial grammars
(with Stepan Kuznetsov, accepted to MOL 2017).
- Recent full versions:
Input-driven languages are linear conjunctive
(appeared in TCS),
Describing the syntax of programming languages using conjunctive and Boolean grammars
Hardest languages for conjunctive and Boolean grammars
- Whale Calf, a parser generator for conjunctive grammars.
Research on automata and their descriptional complexity
Automata are mathematical models of simple computations.
The area of descriptional complexity
is concerned with the size of automata
needed to perform various tasks.
Dr. Okhotin has worked, in particular,
on the following related topics.
- Graph-walking automata:
Reversibility of computations in graph-walking automata
(with Michal Kunc,
slides of a seminar talk in Russian),
- Input-driven pushdown automata (also known as visibly pushdown automata):
State complexity of operations on input-driven pushdown automata
(with Kai Salomaa, JCSS, 2017),
Edit distance neighbourhoods of input-driven pushdown automata
(with Kai Salomaa, CSR 2017,
- Two-way finite automata:
State complexity of operations on two-way deterministic finite automata over a unary alphabet (with M. Kunc, published in TCS),
One-way simulation of two-way finite automata over small alphabets
(with Viliam Geffert,
- Unambiguous finite automata:
Unambiguous finite automata over a unary alphabet (published in I&C).
Research on language equations
Dr. Okhotin's former research topic
were equations with formal languages as unknowns.
His work on the subject was mainly concerned
with establishing the computational completeness
of language equations of a simple form.
Mikhail Ginzburg (undergraduate).
Vladislav Makarov (undergraduate).
Mikhail Mrykhin (undergraduate),
term paper Grammars with context operators and finite transducers.
term paper Variants of LL(k) grammars.
Elizaveta Sazhneva (undergraduate),
term paper Comparison of the expressive power of formal grammars and cellular automata.
Former Ph. D. students
Dr. Artur Jeż
(Ph. D. student at the University of Wrocław, Poland;
supervised jointly with Krzysztof Loryś),
thesis Conjunctive grammars and equations over sets of natural numbers,
defended on the 14th of September, 2010, with distinction;
Polish Prime Minister's Award for an Outstanding Ph. D. thesis (2011).
Dr. Tommi Lehtinen
(Ph. D. student at the University of Turku, 2007–2013),
thesis Numbers and languages,
defended on the 15th of March, 2013.
Dr. Mikhail Barash
(Ph. D. student at the University of Turku, 2011–2015;
supervised jointly with Tero Harju),
thesis Defining contexts in context-free grammars,
defended on the 25th of September, 2015.
Last updated: May A.D. 2017.