Document Open Access Logo

Passive Learning of Deterministic Büchi Automata by Combinations of DFAs

Authors León Bohn , Christof Löding

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.114.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Author Details

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

Funding

  • Bohn, León: Supported by DFG grant LO 1174/7-1.

Cite As Get BibTex

León Bohn and Christof Löding. Passive Learning of Deterministic Büchi Automata by Combinations of DFAs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 114:1-114:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.114

Abstract

We present an algorithm that constructs a deterministic Büchi automaton in polynomial time from given sets of positive and negative example words. This learner constructs multiple DFAs using a polynomial-time active learning algorithm on finite words as black box using an oracle that we implement based on the given sample of ω-words, and combines these DFAs into a single DBA. We prove that the resulting algorithm can learn a DBA for each DBA-recognizable language in the limit by providing a characteristic sample for each DBA-recognizable language. We can only guarantee completeness of our algorithm for the full class of DBAs through characteristic samples that are, in general, exponential in the size of a minimal DBA for the target language. But we show that for each fixed k these characteristic samples are of polynomial size for the class of DBAs in which each subset of pairwise language-equivalent states has size at most k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
Keywords
  • deterministic Büchi automata
  • learning from examples
  • learning in the limit
  • active learning

Metrics

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

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, Udi Boker, and Dana Fisman. Families of DFAs as acceptors of omega-regular languages. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, volume 58 of LIPIcs, pages 11:1-11:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://www.dagstuhl.de/dagpub/978-3-95977-016-3.
  3. 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.
  4. 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.
  5. Dana Angluin, Dana Fisman, and Yaara Shoval. Polynomial identification of ω-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.
  6. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. Google Scholar
  7. Therese Berg and Harald Raffelt. Model checking. In Model-Based Testing of Reactive Systems, volume 3472 of Lecture Notes in Computer Science, chapter 19. Springer, 2005. URL: https://doi.org/10.1007/11498490_25.
  8. Alan W. Biermann and Jerome A. Feldman. On the synthesis of finite-state machines from samples of their behavior. IEEE Trans. Computers, 21(6):592-597, 1972. URL: https://doi.org/10.1109/TC.1972.5009015.
  9. 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, volume 202 of LIPIcs, pages 20:1-20:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.20.
  10. León Bohn and Christof Löding. Constructing deterministic ω-automata from examples by an extension of the rpni algorithm, 2021. URL: http://arxiv.org/abs/2108.03735.
  11. 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
  12. Hugues Calbrix, Maurice Nivat, and Andreas Podelski. Ultimately periodic words of rational ω-languages. In Stephen Brookes, Michael Main, Austin Melton, Michael Mislove, and David Schmidt, editors, Mathematical Foundations of Programming Semantics, pages 554-566, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg. Google Scholar
  13. E Mark Gold. Language identification in the limit. Information and Control, 10(5):447-474, 1967. URL: https://doi.org/10.1016/S0019-9958(67)91165-5.
  14. 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.
  15. John E. Hopcroft and Jeffrey D. Ullman. Formal Languages and their Relation to Automata. Addison-Wesley, 1969. Google Scholar
  16. Malte Isberner, Falk Howar, and Bernhard Steffen. The open-source learnlib - A framework for active automata learning. In Computer Aided Verification - 27th International Conference, CAV 2015, volume 9206 of Lecture Notes in Computer Science, pages 487-495. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21690-4_32.
  17. Damian López and Pedro Garcíía. On the inference of finite state automata from positive and negative data. In Sempere J. In: Heinz J., editor, Topics in Grammatical Inference. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-48395-4_4.
  18. 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.
  19. 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.
  20. 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.
  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. Ronald L. Rivest and Robert E. Schapire. Inference of finite automata using homing sequences. In Machine Learning: From Theory to Applications, volume 661 of Lecture Notes in Computer Science, pages 51-73. Springer, 1993. Google Scholar
  23. 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.
  24. Wolfgang Thomas. Automata on Infinite Objects, pages 133-191. MIT Press, Cambridge, MA, USA, 1991. Google Scholar
  25. 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. Google Scholar
  26. Boris A. Trakhtenbrot and Y.M. Barzdin. Finite Automata: Behavior and Synthesis. North-Holland Publishing Company, Amsterdam, 1973. Google Scholar
  27. Sicco Verwer and Christian A. Hammerschmidt. flexfringe: A passive automaton learning package. In 2017 IEEE International Conference on Software Maintenance and Evolution, ICSME 2017, pages 638-642. IEEE Computer Society, 2017. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8090480.
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