6 citations · 6 across the 6 of their papers we have counts for
6 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 C…
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…
On the rank of the communication matrix for deterministic two-way finite automata
Semyon Petrov, Fedor Petrov, Alexander Okhotin
The communication matrix for two-way deterministic finite automata (2DFA) with states is defined for an automaton over a full alphabet of all possible symbols: its r…
Sweeping Permutation Automata
Maria Radionova, Alexander Okhotin
This paper introduces sweeping permutation automata, which move over an input string in alternating left-to-right and right-to-left sweeps and have a bijective transition function.…