2 papers
cs.FL2025
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…
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…