Document Open Access Logo

Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm

Authors León Bohn , Christof Löding

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.20.pdf
  • Filesize: 0.84 MB
  • 18 pages

Document Identifiers

Author Details

León Bohn
  • RWTH Aachen University, Germany
Christof Löding
  • RWTH Aachen University, Germany

Cite As Get BibTex

León Bohn and Christof Löding. Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.20

Abstract

The RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite automata from finite sets of negative and positive example words. We propose and analyze an extension of this algorithm to deterministic ω-automata with different types of acceptance conditions. In order to obtain this generalization of RPNI, we develop algorithms for the standard acceptance conditions of ω-automata that check for a given set of example words and a deterministic transition system, whether these example words can be accepted in the transition system with a corresponding acceptance condition. Based on these algorithms, we can define the extension of RPNI to infinite words. We prove that it can learn all deterministic ω-automata with an informative right congruence in the limit with polynomial time and data. We also show that the algorithm, while it can learn some automata that do not have an informative right congruence, cannot learn deterministic ω-automata for all regular ω-languages in the limit. Finally, we also prove that active learning with membership and equivalence queries is not easier for automata with an informative right congruence than for general deterministic ω-automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
Keywords
  • deterministic omega-automata
  • learning from examples
  • learning in the limit
  • constructing acceptance conditions
  • active learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87-106, 1987. URL: https://doi.org/10.1016/0890-5401(87)90052-6.
  2. Dana Angluin and Dana Fisman. Learning regular omega languages. Theor. Comput. Sci., 650:57-72, 2016. URL: https://doi.org/10.1016/j.tcs.2016.07.031.
  3. Dana Angluin and Dana Fisman. Regular omega-languages with an informative right congruence. In Proceedings Ninth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2018, Saarbrücken, Germany, 26-28th September 2018, volume 277 of EPTCS, pages 265-279, 2018. URL: https://doi.org/10.4204/EPTCS.277.19.
  4. Dana Angluin, Dana Fisman, and Yaara Shoval. Polynomial identification of ømega-automata. In Armin Biere and David Parker, editors, Tools and Algorithms for the Construction and Analysis of Systems - 26th International Conference, TACAS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25-30, 2020, Proceedings, Part II, volume 12079 of Lecture Notes in Computer Science, pages 325-343. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45237-7_20.
  5. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. Google Scholar
  6. Andreas Birkendorf, Andreas Böker, and Hans Simon. Learning deterministic finite automata from smallest counterexamples. SIAM J. Discrete Math., 13:465-491, January 2000. URL: https://doi.org/10.1137/S0895480198340943.
  7. J Richard Büchi. On a decision method in restricted second order arithmetic, logic, methodology and philosophy of science (proc. 1960 internat. congr.), 1962. Google Scholar
  8. Rafael C. Carrasco and José Oncina. Learning stochastic regular grammars by means of a state merging method. In Grammatical Inference and Applications, Second International Colloquium, ICGI-94, Alicante, Spain, September 21-23, 1994, Proceedings, volume 862 of Lecture Notes in Computer Science, pages 139-152. Springer, 1994. URL: https://doi.org/10.1007/3-540-58473-0_144.
  9. Olivier Carton and Ramón Maceiras. Computing the rabin index of a parity automaton. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 33(6):495-505, 1999. URL: http://www.numdam.org/item/ITA_1999__33_6_495_0/.
  10. Colin De La Higuera. Characteristic sets for polynomial grammatical inference. In Laurent Miclet and Colin de la Higuera, editors, Grammatical Interference: Learning Syntax from Sentences, pages 59-71, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. Google Scholar
  11. Stefan Dziembowski, Marcin Jurdziński, and Igor Walukiewicz. How much memory is needed to win infinite games? In Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, LICS '97, pages 99-110, Los Alamitos, California, 1997. IEEE Computer Society Press. URL: https://doi.org/10.1109/lics.1997.614939.
  12. E. Mark Gold. Complexity of automaton identification from given data. Inf. Control., 37(3):302-320, 1978. URL: https://doi.org/10.1016/S0019-9958(78)90562-4.
  13. John E. Hopcroft and Jeffrey D. Ullman. Formal Languages and their Relation to Automata. Addison-Wesley, 1969. Google Scholar
  14. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  15. Christof Löding and Anton Pirogov. Determinization of Büchi automata: Unifying the approaches of Safra and Muller-Schupp. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132 of LIPIcs, pages 120:1-120:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.120.
  16. Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Inf. Comput., 118(2):316-326, 1995. URL: https://doi.org/10.1006/inco.1995.1070.
  17. Hua Mao, Yingke Chen, Manfred Jaeger, Thomas D. Nielsen, Kim G. Larsen, and Brian Nielsen. Learning probabilistic automata for model checking. In Eighth International Conference on Quantitative Evaluation of Systems, QEST 2011, Aachen, Germany, 5-8 September, 2011, pages 111-120. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/QEST.2011.21.
  18. Philipp J. Meyer, Salomon Sickert, and Michael Luttenberger. 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, pages 578-586, 2018. URL: https://doi.org/10.1007/978-3-319-96145-3_31.
  19. Jakub Michaliszyn and Jan Otop. Learning deterministic automata on infinite words. In ECAI 2020 - 24th European Conference on Artificial Intelligence, volume 325 of Frontiers in Artificial Intelligence and Applications, pages 2370-2377. IOS Press, 2020. URL: https://doi.org/10.3233/FAIA200367.
  20. José Oncina, Pedro García, and Enrique Vidal. Learning subsequential transducers for pattern recognition interpretation tasks. IEEE Trans. Pattern Anal. Mach. Intell., 15(5):448-458, 1993. URL: https://doi.org/10.1109/34.211465.
  21. Jose Oncina and Pedro García. Inferring regular languages in polynomial update time. World Scientific, January 1992. URL: https://doi.org/10.1142/9789812797902_0004.
  22. Nir Piterman. From nondeterministic Büchi and Streett automata to deterministic parity automata. In Proceedings of the 21st IEEE Symposium on Logic in Computer Science (LICS 2006), pages 255-264. IEEE Computer Society, 2006. URL: https://doi.org/10.2168/LMCS-3(3:5)2007.
  23. Shmuel Safra. On the complexity of omega-automata. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FoCS '88, pages 319-327, Los Alamitos, California, 1988. IEEE Computer Society Press. URL: https://doi.org/10.1109/SFCS.1988.21948.
  24. Sven Schewe. Tighter bounds for the determinisation of Büchi automata. In Proceedings of Foundations of Software Science and Computational Structures, 12th International Conference, FOSSACS 2009, volume 5504 of Lecture Notes in Computer Science, pages 167-181. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-00596-1_13.
  25. Sven Schewe. Beyond Hyper-Minimisation - Minimising DBAs and DPAs is NP-Complete. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), volume 8 of Leibniz International Proceedings in Informatics (LIPIcs), pages 400-411, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.400.
  26. Wolfgang Thomas. Automata on Infinite Objects, page 133–191. MIT Press, Cambridge, MA, USA, 1991. Google Scholar
  27. Wolfgang Thomas. Facets of synthesis: Revisiting Church’s problem. In Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2009, volume 5504 of Lecture Notes in Computer Science, pages 1-14. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-00596-1_1.
  28. Wieslaw Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science, 200(1):135-183, 1998. URL: https://doi.org/10.1016/S0304-3975(98)00009-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact