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

Published on: September 17, 2015

Submitted 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

15 Documents citing this article

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, eScholarship (California Digital Library), Formal Analysis of AI-Based Autonomy: From Modeling to Runtime Assurance, pp. 311-330, 2021, 10.1007/978-3-030-88494-9_19, https://escholarship.org/uc/item/0q02f9xx.

Loris D'Antoni;Margus Veanes, 2021, Automata modulo theories, Communications of the ACM, 64, 5, pp. 86-95, 10.1145/3419404, https://doi.org/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, Lecture notes in computer science, Combining Black-Box and White-Box Techniques for Learning Register Automata, pp. 563-588, 2019, 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, arXiv (Cornell University), 23, 1, pp. 1-29, 10.1007/s10009-019-00544-0, https://arxiv.org/abs/1605.07805.

Kaizaburo Chubachi;Diptarama Hendrian;Ryo Yoshinaka;Ayumi Shinohara, 2019, Query Learning Algorithm for Residual Symbolic Finite Automata, arXiv (Cornell University), 305, pp. 140-153, 10.4204/eptcs.305.10.

Dana Angluin;Dana Fisman, 2018, Regular omega-Languages with an Informative Right Congruence, arXiv (Cornell University), 277, pp. 265-279, 10.4204/eptcs.277.19.

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

George Argyros;Loris D’Antoni, Lecture notes in computer science, The Learnability of Symbolic Automata, pp. 427-445, 2018, 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, On the Quantitative Semantics of Regular Expressions over Real-Valued Signals, pp. 189-206, 2017, 10.1007/978-3-319-65765-3_11, https://hal.archives-ouvertes.fr/hal-01552132.

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, UCL Discovery (University College London), 52, 1, pp. 613-625, 10.1145/3093333.3009879, https://discovery.ucl.ac.uk/id/eprint/10085264/.

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

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

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1822 times.

This article's PDF has been downloaded 604 times.