6 citations · 6 across the 6 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.FL2024
A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
Semyon Petrov, Alexander Okhotin
This paper establishes a lower bound on the number of states necessary in the worst case to simulate an -state two-way nondeterministic finite automaton (2NFA) by a one-way unam…
cs.FL2024
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…
cs.FL2024
A hierarchy of reversible finite automata
Maria Radionova, Alexander Okhotin
In this paper, different variants of reversible finite automata are compared, and their hierarchy by the expressive power is established. It is shown that one-way reversible automa…