8 citations · 13 across the 14 of their papers we have counts for
14 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 LL(k) linear conjunctive grammars
Ilya Olkhovsky, Alexander Okhotin
Linear conjunctive grammars are a family of formal grammars with an explicit conjunction operation allowed in the rules, which is notable for its computational equivalence fo one-w…
Homomorphisms on graph-walking automata
Olga Martynova, Alexander Okhotin
Graph-walking automata (GWA) are a model for graph traversal using finite-state control: these automata move between the nodes of an input graph, following its edges. This paper in…
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…
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…
Grammars with two-sided contexts
Mikhail Barash, Alexander Okhotin
In a recent paper (M. Barash, A. Okhotin, "Defining contexts in context-free grammars", LATA 2012), the authors introduced an extension of the context-free grammars equipped with a…
On equations over sets of integers
Artur Jeż, Alexander Okhotin
Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of uni…
Nondeterministic State Complexity of Positional Addition
Galina Jirásková, Alexander Okhotin
Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved…
Representing a P-complete problem by small trellis automata
Alexander Okhotin
A restricted case of the Circuit Value Problem known as the Sequential NOR Circuit Value Problem was recently used to obtain very succinct examples of conjunctive grammars, Boolean…