14 citations · 15 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
On Semantically-Deterministic Automata
Bader Abu Radi, Orna Kupferman
A nondeterministic automaton is semantically deterministic (SD) if different nondeterministic choices in the automaton lead to equivalent states. Semantic determinism is interestin…
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…
Canonicity in GFG and Transition-Based Automata
Bader Abu Radi, Orna Kupferman
Minimization of deterministic automata on finite words results in a {\em canonical\/} automaton. For deterministic automata on infinite words, no canonical minimal automaton exists…