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

DOI10.3233/FI-222152arXiv2211.08787OpenAlexW4383956509MaRDI QIDQ6094518FDOQ6094518

Authors: Christof Löding 

Publication date: 14 September 2023

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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.

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

Recommendations

• Efficient minimization of deterministic weak \(\omega\)-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

zbMATH Keywords

learningminimizationdeterministic \(\omega\)-automatadon't care words

Mathematics Subject Classification ID

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

Cites Work

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

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)