I am a Russian mathematician in the Finnish service.
I have been working
at the Department of Mathematics and Statistics
of the University of Turku,
first as a research fellow of the Academy of Finland (2006–2011),
and then as a researcher of the Turku Collegium for Science and Medicine (2012–2014),
and currently as a researcher on a temporary contract (since 2015).
My research interests belong to the area
of formal language and automata theory,
and my main subjects are
formal grammars and their parsing algorithms,
language equations in connection with computability,
and descriptional complexity of finite automata.
I received my education
at Moscow State University, Russia (1996–2001),
and at Queen's University, Canada (2001–2004),
and got a habilitation from the University of Turku (2009).
- My curriculum vitae:
(5 February 2016)
- Looking for a professor position;
also interested in employment as a short-term visiting professor.
- Current status of my refereeing queue:
4 papers under review.
- My office is Quantum 395.
- Current status of the Formal Grammars draft:
334 pages, 59 figures, 514 names in the name index.
- How to pronounce my family name:
as [o'hotin] or as [ə'hotin];
in particular, as Ohotin in English and in Finnish,
and as Ochotin in Western Slavic languages and in German.
Research on formal grammars
My research on grammars
began with understanding context-free grammars
as a logic for representing syntax,
which prompted me to investigate
the power of Boolean connectives in this logic.
This outlook led me
to conjunctive grammars,
which allow a conjunction operation in their rules,
and to Boolean grammars,
which further allow the negation.
My subsequent research has shown
that the main practically relevant properties of ordinary (context-free) grammars,
including most of the parsing algorithms,
equally hold for Boolean grammars.
These developments significantly change
the perspective on formal grammars in general,
and now my mission is to work out
an up-to-date theory of formal grammars.
- A talk on formal grammars in general:
Formal grammars after the Cuban missile crisis
(in English: May 2014, Umeå, Sweden,
in Russian: September 2014, Moscow, Russia).
- 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, 9 (2013), 27-59;
author's pre-acceptance draft).
- Nine open problems for conjunctive and Boolean grammars
(#2 solved in 2007, #3 solved in 2009).
- Recent new manuscripts:
Generalized LR parsing for grammars with contexts
(with Mikhail Barash, presented at CSR 2015).
- Recent full versions:
Improved normal form for grammars with one-sided contexts
(appeared in TCS),
Grammars with two-sided contexts
(with Mikhail Barash, appeared in TCS),
Input-driven languages are linear conjunctive
(accepted to TCS).
Research on language equations
Equations with formal languages as unknowns
naturally arise when reasoning about sets of strings,
and they have been used in many applied areas of computer science.
These applications would benefit
from a general theory of language equations.
I have been working towards such a theory,
exploring the relations between language equations and computation,
and tracing the border between their decidability and undecidability.
The latest findings are that, in short,
almost all language equations are computationally complete,
including those over a one-letter alphabet
and with concatenation as the only operation.
Research on descriptional complexity of automata
It is well-known that
converting a nondeterministic finite automaton (NFA)
to an equivalent deterministic one (DFA)
requires exponentially many states;
representing a Kleene star of a DFA
also leads to an exponential blowup
in the size of description.
For ordinary DFAs and NFAs,
all problems of this kind have long been solved.
I am occasionally investigating similar problems
for a few related models, such as
unambiguous finite automata (UFA),
two-way finite automata (2DFA, 2NFA)
and input-driven pushdown automata (IDPDA).
Students, current and former
- 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.
- Whale Calf, a parser generator for conjunctive grammars.
- dfalib, a C++ class library for basic operations on finite automata.
(Announced in July 2012)
Travel data: countries visited; places visited (KML). (Generated on 4 January 2016)
- I have an unusual hobby: I do not take pictures.
However, before I took up this hobby,
I enjoyed photography like everyone else.
- From CIAA 2004 conference, Kingston, Ontario, Canada, July 22–24, 2004.
- From AFL 2005 conference, Dobogoko, Hungary, May 17–20, 2005.
- From DCFS 2005 workshop, Como, Italy, June 30–July 2, 2005.
- From DLT 2005
(second part) conference, Palermo, Italy, July 4–8, 2005.
- From Workshop on Fibonacci Words, Turku, Finland, September 27–30, 2006.
- From DLT 2007 conference, Turku, Finland, June 3–6, 2007.
- From UC 2011 conference, Turku, Finland, June 6–10, 2011.
- From RuFiDiM 2012 conference, Turku, Finland, September 25–28, 2012.
- Not from conferences:
Good Friday procession (Tarragona, Spain, April 14, 2006),
Last updated: August A.D. 2015.