1 citations · 1 across the 7 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
cs.FL2022
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).…
cs.FL2022
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…
cs.FL2022★ 1 cited
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}…