8 citations · 13 across the 14 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
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}…