2 citations · 4 across the 7 of their papers we have counts for
9 papers
Non-closure under complementation for unambiguous linear grammars
Olga Martynova, Alexander Okhotin
The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To…
The maximum length of shortest accepted strings for direction-determinate two-way finite automata
Olga Martynova, Alexander Okhotin
It is shown that, for every , the maximum length of the shortest string accepted by an -state direction-determinate two-way finite automaton is exactly $\binom{n}…
On the determinization of event-clock input-driven pushdown automata
Mizuhito Ogawa, Alexander Okhotin
Input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) are a subclass of deterministic pushdown automata and a superclass of the paren…
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…