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