8 citations · 13 across the 14 of their papers we have counts for
5 papers · 1 filter
Rational index of bounded-oscillation languages
Ekaterina Shemetova, Alexander Okhotin, Semyon Grigorev
The rational index of a context-free language is a function , such that for each regular language recognized by an automaton with states, the intersection of …
Describing the syntax of programming languages using conjunctive and Boolean grammars
Alexander Okhotin
A classical result by Floyd ("On the non-existence of a phrase structure grammar for ALGOL 60", 1962) states that the complete syntax of any sensible programming language cannot be…
Input-driven automata on well-nested infinite strings: automata-theoretic and topological properties
Alexander Okhotin, Victor L. Selivanov
Automata operating on strings of nested brackets, known as input-driven pushdown automata, and as visibly pushdown automata, have been studied since the 1980s. They were extended t…
The hardest language for grammars with context operators
Mikhail Mrykhin, Alexander Okhotin
In 1973, Greibach ("The hardest context-free language", SIAM J. Comp., 1973) constructed a context-free language with the property that every context-free language can be red…
State complexity of halting, returning and reversible graph-walking automata
Olga Martynova, Alexander Okhotin
Graph-walking automata (GWA) traverse graphs by moving between the nodes following the edges, using a finite-state control to decide where to go next. It is known that every GWA ca…