1 citations · 1 across the 7 of their papers we have counts for
7 papers
From regular expressions to deterministic finite automata: states are necessary and sufficient
Olga Martynova, Alexander Okhotin
It is proved that every regular expression of alphabetic width , that is, with occurrences of symbols of the alphabet, can be transformed into a deterministic finite automat…
Nondeterministic tree-walking automata are not closed under complementation
Olga Martynova, Alexander Okhotin
It is proved that the family of tree languages recognized by nondeterministic tree-walking automata is not closed under complementation, solving a problem raised by Bojańczyk and C…
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
Olga Martynova
This paper proves the decidability of the emptiness problem for two models which recognize graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata).…
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}…
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…
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…