On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words

DOI10.3233/FI-222152MaRDI QIDQ6094518zbMATH OpenOpenAlexFDO

Authors Christof Löding

Publication date 14 September 2023

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.08787

zbMATH Keywords

deterministic \(\omega\)-automatadon't care wordslearningminimization

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Abstract: We study minimization problems for deterministic $omega$-automata in the presence of don't care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don't care words). We then analyze languages of don't care words with a trivial right-congruence. For such sets of don't care words it is known that weak deterministic B"uchi automata (WDBA) have a unique minimal automaton that can be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don't care minimization results for WDBA do not extend to deterministic $omega$-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don't care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don't care words with trivial right-congruence.

Recommendations

• Efficient minimization of deterministic weak -automata
• Optimal state reductions of automata with partially specified behaviors
• On the minimization problem for \(\omega \)-automata
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete
• Optimal state reductions of automata with partially specified behaviors

Cites work

• Automata, logics, and infinite games. A guide to current research
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete
• Computer aided verification. 18th international conference, CAV 2006, Seattle, WA, USA, August 17--20, 2006. Proceedings.
• Computing the Rabin Index of a Parity Automaton
• Constructing deterministic -automata from examples by an extension of the RPNI algorithm
• Efficient minimization of deterministic weak -automata
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 48095 (Why is no real title available?)
• scientific article; zbMATH DE number 3471986 (Why is no real title available?)
• scientific article; zbMATH DE number 1555955 (Why is no real title available?)
• Learning regular omega languages
• Learning regular sets from queries and counterexamples
• New optimizations and heuristics for determinization of Büchi automata
• On syntactic congruences for \(\omega\)-languages
• On the learnability of infinitary regular sets
• On ω-regular sets
• Polynomial identification of \(\omega \)-automata
• Reducibility among combinatorial problems
• State Reduction in Incompletely Specified Finite-State Machines

This page was built for publication: On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094518)