Minimal History-Deterministic Co-Büchi Automata: Congruences and Passive Learning

2025/05/20 by Christof Löding, Igor Walukiewicz, Löding, Christof +1 · 1 voice · 1 citation
Computer Science · #cs.FL

paper · pdf · doi:10.48550/arxiv.2505.14304

Abstract

Abu Radi and Kupferman (2019) demonstrated the efficient minimization of history-deterministic (transition-based) co-Büchi automata, building on the results of Kuperberg and Skrzypczak (2015). We give a congruence-based description of these minimal automata, and a self-contained proof of its correctness. We use this description based on congruences to create a passive learning algorithm that can learn minimal history-deterministic co-Büchi automata from a set of labeled example words. The algorithm runs in polynomial time on a given set of examples, and there is a characteristic set of examples of polynomial size for each minimal history-deterministic co-Büchi automaton.

Citations

• On the Synthesis of Finite-State Machines from Samples of Their Behavior

Cited by

• Transition-based vs stated-based acceptance for automata over infinite words

Discussions

• Christof L\"oding, Igor Walukiewicz: Minimal History-Deterministic Co-Buchi Automata: Congruences and Passive Learning https://arxiv.org/abs/2505.14304 https://arxiv.org/pdf/2505.14304 https://arxiv.o [bsky, 0 points, 1 comments]

Related

• Characterizing the Polynomial-Time Minimizable ω-Automata
• Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
• The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
• Efficient Learning of Weak Deterministic Büchi Automata
• History-Deterministic Parity Automata: Games, Complexity, and the 2-Token Theorem