1 citations · 1 across the 4 of their papers we have counts for
4 papers
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}…
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…