Learning Regular Languages over Large Ordered Alphabets

Irini-Eleftheria Mens; Oded Maler

doi:10.2168/LMCS-11(3:13)2015

Irini-Eleftheria Mens ; Oded Maler - Learning Regular Languages over Large Ordered Alphabets

lmcs:1589 - Logical Methods in Computer Science, September 17, 2015, Volume 11, Issue 3 - https://doi.org/10.2168/LMCS-11(3:13)2015

Learning Regular Languages over Large Ordered AlphabetsArticle

Authors: Irini-Eleftheria Mens ; Oded Maler

This work is concerned with regular languages defined over large alphabets, either infinite or just too large to be expressed enumeratively. We define a generic model where transitions are labeled by elements of a finite partition of the alphabet. We then extend Angluin's L* algorithm for learning regular languages from examples for such automata. We have implemented this algorithm and we demonstrate its behavior where the alphabet is a subset of the natural or real numbers. We sketch the extension of the algorithm to a class of languages over partially ordered alphabets.

https://doi.org/10.2168/LMCS-11(3:13)2015

Source: arXiv.org:1506.00482

Volume: Volume 11, Issue 3

Secondary volumes: Selected Papers of the 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2014)

Published on: September 17, 2015

Imported on: November 14, 2014

Keywords: Computer Science - Logic in Computer Science, Computer Science - Artificial Intelligence, Computer Science - Formal Languages and Automata Theory

Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

16 Documents citing this article

Yutaro Numaya;Yoshito Kawasaki;Ryo Yoshinaka;Ayumi Shinohara, 2025, Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets, Lecture notes in computer science, pp. 211-224, 10.1007/978-3-031-82697-9_16.

Natasha Yogananda Jeppu;Tom Melham;Daniel Kroening, 2022, Enhancing active model learning with equivalence checking using simulation relations, Formal Methods in System Design, 61, 2-3, pp. 164-197, 10.1007/s10703-023-00433-y, https://doi.org/10.1007/s10703-023-00433-y.

Hazem Torfah;Sebastian Junges;Daniel J. Fremont;Sanjit A. Seshia, 2021, Formal Analysis of AI-Based Autonomy: From Modeling to Runtime Assurance, Lecture notes in computer science, pp. 311-330, 10.1007/978-3-030-88494-9_19.

Loris D'Antoni;Margus Veanes, 2021, Automata modulo theories, Communications of the ACM, 64, 5, pp. 86-95, 10.1145/3419404.

Dana Angluin;Dana Fisman, 2020, Regular ω-languages with an informative right congruence, Information and Computation, 278, pp. 104598, 10.1016/j.ic.2020.104598.

Falk Howar;Bengt Jonsson;Frits Vaandrager, 2019, Combining Black-Box and White-Box Techniques for Learning Register Automata, Lecture notes in computer science, pp. 563-588, 10.1007/978-3-319-91908-9_26, https://doi.org/10.1007/978-3-319-91908-9_26.

Georgios Giantamidis;Stavros Tripakis;Stylianos Basagiannis, 2019, Learning Moore machines from input–output traces, International Journal on Software Tools for Technology Transfer, 23, 1, pp. 1-29, 10.1007/s10009-019-00544-0.

Kaizaburo Chubachi;Diptarama Hendrian;Ryo Yoshinaka;Ayumi Shinohara, 2019, Query Learning Algorithm for Residual Symbolic Finite Automata, Electronic Proceedings in Theoretical Computer Science, 305, pp. 140-153, 10.4204/eptcs.305.10, https://doi.org/10.4204/eptcs.305.10.

Dana Angluin;Dana Fisman, 2018, Regular omega-Languages with an Informative Right Congruence, Electronic Proceedings in Theoretical Computer Science, 277, pp. 265-279, 10.4204/eptcs.277.19, https://doi.org/10.4204/eptcs.277.19.

Falk Howar;Bernhard Steffen, 2018, Active Automata Learning in Practice, Lecture notes in computer science, pp. 123-148, 10.1007/978-3-319-96562-8_5.

George Argyros;Loris D’Antoni, 2018, The Learnability of Symbolic Automata, Lecture notes in computer science, pp. 427-445, 10.1007/978-3-319-96145-3_23, https://doi.org/10.1007/978-3-319-96145-3_23.

Alexey Bakhirkin;Thomas Ferrère;Oded Maler;Dogan Ulus, 2017, On the Quantitative Semantics of Regular Expressions over Real-Valued Signals, Lecture notes in computer science, pp. 189-206, 10.1007/978-3-319-65765-3_11.

Huimin Zhang;Lei Feng;Naiqi Wu;Zhiwu Li, 2017, Integration of Learning-Based Testing and Supervisory Control for Requirements Conformance of Black-Box Reactive Systems, IEEE Transactions on Automation Science and Engineering, 15, 1, pp. 2-15, 10.1109/tase.2017.2693995.

Joshua Moerman;Matteo Sammartino;Alexandra Silva;Bartek Klin;Michał Szynwelski, 2017, Learning nominal automata, ACM SIGPLAN Notices, 52, 1, pp. 613-625, 10.1145/3093333.3009879.

Samuel Drews;Loris D’Antoni, 2017, Learning Symbolic Automata, Lecture notes in computer science, pp. 173-189, 10.1007/978-3-662-54577-5_10.

Joshua Moerman;Matteo Sammartino;Alexandra Silva;Bartek Klin;Michał Szynwelski, 2016, Learning nominal automata, arXiv (Cornell University), pp. 613-625, 10.1145/3009837.3009879, http://arxiv.org/abs/1607.06268.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3263 times.

This article's PDF has been downloaded 819 times.