2 papers
cs.FL2025
A Hierarchy of Nondeterminism
Bader Abu Radi, Orna Kupferman, Ofer Leshkowitz
We study three levels in a hierarchy of nondeterminism: A nondeterministic automaton is determinizable by pruning (DBP) if we can obtain a deterministic automaton equ…
cs.FL2025
Characterizing the Polynomial-Time Minimizable -Automata
Bader Abu Radi, Rüdiger Ehlers
A central question in the theory of automata is which classes of automata can be minimized in polynomial time. We close the remaining gaps for deterministic and history-determinist…