Alexander Okhotin

Alexander Okhotin (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.

Research on formal grammars

Formal grammars are mathematical models of syntax. Dr. Okhotin introduced and studied two extensions of ordinary (“context-free”) grammars: conjunctive 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.

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.

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.

Recent teaching

Current students

Former Ph. D. students

Other duties

General information



Last updated: May A.D. 2017.