4 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…
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…
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…
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…