3 papers
cs.FL2025
From LTL to COCOA without Detours
Rüdiger Ehlers, Ayrat Khalimov
Chains of co-Büchi automata (COCOA) have recently been introduced as a new canonical representation of omega-regular languages. The co-Büchi automata in a chain assign each omega…
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…
cs.FL2025
Rerailing Automata
Rüdiger Ehlers
In this paper, we introduce rerailing automata for -regular languages. They generalize both deterministic parity (DPW) and minimized history-deterministic co-Büchi automata (w…