{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:27:25Z","timestamp":1777645645757,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2023,7,7]]},"abstract":"<jats:p>We study minimization problems for deterministic \u03c9-automata in the presence of don\u2019t care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don\u2019t 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\u2019t care words). We then analyze languages of don\u2019t care words with a trivial right-congruence. For such sets of don\u2019t care words it is known that weak deterministic B\u00fcchi 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\u2019t care minimization results for WDBA do not extend to deterministic \u03c9-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don\u2019t 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\u2019t care words with trivial right-congruence.<\/jats:p>","DOI":"10.3233\/fi-222152","type":"journal-article","created":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T10:12:23Z","timestamp":1689070343000},"page":"69-91","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Minimization and Learning of Deterministic \u03c9-Automata in the Presence of Don\u2019t Care Words"],"prefix":"10.1177","volume":"189","author":[{"given":"Christof","family":"L\u00f6ding","sequence":"first","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, Germany, ,"}]},{"given":"Max Philip","family":"Stachon","sequence":"additional","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, Germany, ,"}]}],"member":"179","published-online":{"date-parts":[[2023,7,7]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-222152","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-222152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:32:50Z","timestamp":1777444370000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-222152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,7,7]]}},"alternative-id":["10.3233\/FI-222152"],"URL":"https:\/\/doi.org\/10.3233\/fi-222152","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,7]]}}}