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

• Autorzy: Löding Christof , Stachon Max Philip

Identyfikatory

DOI

10.3233/FI-222152

• Języki publikacji: EN

Abstrakty

EN

We study minimization problems for deterministic ω-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üchi 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 ω-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.

Słowa kluczowe

EN

deterministic ω-automata; don’t care words; learning; minimization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 1.
• Strony: 69--90
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Löding Christof

• Department of Computer Science RWTH Aachen University, Germany

autor

Stachon Max Philip

• Department of Computer Science RWTH Aachen University, Germany

Bibliografia

• [1] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
• [2] Angluin D. Learning regular sets from queries and counterexamples. Information and Computation, 1987. 75(2):87 - 106. doi: https://doi.org/10.1016/0890-5401(87)90052-6. URL http://www.sciencedirect.com/science/article/pii/0890540187900526.
• [3] Pfleeger CP. State Reduction in Incompletely Specified Finite-State Machines. IEEE Transactions on Computers, 1973. C-22(12):87-106.
• [4] Schewe S. Beyond Hyper-Minimisation—Minimising DBAs and DPAs is NP-Complete. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010 .
• [5] Krishnan SC, Puri A, Brayton RK. Deterministic w Automata vis-a-vis Deterministic Buchi Automata. In: Algorithms and Computation, 5th International Symposium, ISAAC ’94, Beijing, P. R. China, August 25-27, 1994, Proceedings, volume 834 of Lecture Notes in Computer Science. Springer, 1994 pp. 378-386. doi:10.1007/3-540-58325-4\ 202. URL https://doi.org/10.1007/3-540-58325-4\_202.
• [6] Thomas W. Automata on Infinite Objects. In: Leeuwen JV (ed.), Formal Models and Semantics, Handbook of Theoretical Computer Science, pp. 133-191. Elsevier, Amsterdam. ISBN 978-0-444-88074-1, 1990. doi: https://doi.org/10.1016/B978-0-444-88074-1.50009-3. URL https://www.sciencedirect.com/science/article/pii/B9780444880741500093.
• [7] Grӓdel E, Thomas W, Wilke T (eds.). Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002. ISBN 3-540-00388-6. doi:10.1007/3-540-36387-4. URL https://doi.org/10.1007/3-540-36387-4.
• [8] Lӧding C. Efficient minimization of deterministic weak ω-automata. Information Processing Letters, 2001. 79(3):105 - 109. doi:https://doi.org/10.1016/S0020-0190(00)00183-6. URL http://www.sciencedirect.com/science/article/pii/S0020019000001836.
• [9] L Staiger KW. Automatentheoretische und Automatenfreie Charakterisierung Toplogischer Klassen Regulӓrer Folgenmengen. Elektron. Informationsverarbeitung und Kybernetik EIK 10, 1974. p. 379 392.
• [10] Maler O, Staiger L. On syntactic congruences for omega-languages. Theoretical Computer Science, 1997. 183(1):93-112. doi:https://doi.org/10.1016/S0304-3975(96)00312-X. Formal Language Theory, URL https://www.sciencedirect.com/science/article/pii/S030439759600312X.
• [11] Wagner K. On omega-regular sets. Information and Control, 1979. 43(2):123-177. doi:https://doi. org/10.1016/S0019-9958(79)90653-3. URL https://www.sciencedirect.com/science/article/pii/S0019995879906533.
• [12] Maler O, Pnueli A. On the Learnability of Infinitary Regular Sets. Information and Computation, 1995. 118(2):316 - 326. doi:https://doi.org/10.1006/inco.1995.1070. URL http://www.sciencedirect.com/science/article/pii/S089054018571070X.
• [13] Angluin D, Fisman D. Learning regular omega languages. Theor. Comput. Sci., 2016. 650:57-72. doi: 10.1016/j.tcs.2016.07.031. URL https://doi.org/10.1016/j.tcs.2016.07.031.
• [14] Eisinger J, Klaedtke F. Don’t Care Words with an Application to the Automata-Based Approach for Real Addition. In: Computer Aided Verification, 18th International Conference, CAV 2006, volume 4144 of Lecture Notes in Computer Science. Springer. ISBN 3-540-37406-X, 2006 pp. 67-80. doi: 10.1007/11817963. URL https://doi.org/10.1007/11817963.
• [15] Angluin D, Fisman D. Regular omega-Languages with an Informative Right Congruence. Electronic Proceedings in Theoretical Computer Science, 2018. 277:265279. doi:10.4204/eptcs.277.19. URL http://dx.doi.org/10.4204/EPTCS.277.19.
• [16] Carton O, Maceiras R. Computing the Rabin Index of a Parity Automaton. RAIRO Theoretical Informatics and Applications, 1999. 33(6):495-506.
• [17] Lӧding C, Pirogov A. New Optimizations and Heuristics for Determinization of Büchi Automata. In: Proceedings of the 17th International Symposium on Automated Technology for Verification and Analysis (ATVA’19), volume 11781 of Lecture Notes in Computer Science. Springer, 2019 .
• [18] Bohn L, Lӧding C. Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021 pp. 20:1-20:18. doi:10.4230/LIPIcs.MFCS.2021.20. URL https://doi.org/10.4230/LIPIcs.MFCS.2021.20.
• [19] Angluin D, Fisman D, Shoval Y. Polynomial Identification of omega-Automata. CoRR, 2022. abs/2209.09336. doi:10.48550/arXiv.2209.09336. 2209.09336, URL https://doi.org/10.48550/arXiv.2209.09336.
• [20] Karp RM. Reducibility among Combinatorial Problems, pp. 85-103. Springer US, Boston, MA. ISBN 978-1-4684-2001-2, 1972.
• [21] Meyer PJ, Sickert S, Luttenberger M. Strix: Explicit Reactive Synthesis Strikes Back! In: Computer Aided Verification - 30th International Conference, CAV 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, Part I. 2018 pp. 578-586. doi: 10.1007/978-3-319-96145-3\ 31. URL https://doi.org/10.1007/978-3-319-96145-3\_31