Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
10-2011
Abstract
In inference of untimed regular languages, given an unknown language to be inferred, an automaton is constructed to accept the unknown language from answers to a set of membership queries each of which asks whether a string is contained in the unknown language. One of the most well-known regular inference algorithms is the L* algorithm, proposed by Angluin in 1987, which can learn a minimal deterministic finite automaton (DFA) to accept the unknown language. In this work, we propose an efficient polynomial time learning algorithm, TL*, for timed regular language accepted by event-recording automata. Given an unknown timed regular language, TL* first learns a DFA accepting the untimed version of the timed language, and then passively refines the DFA by adding time constraints. We prove the correctness, termination, and minimality of the proposed TL* algorithm.
Discipline
Programming Languages and Compilers | Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
Proceedings of the 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14
First Page
463
Last Page
472
ISBN
9783642243714
Identifier
10.1007/978-3-642-24372-1_35
Publisher
Springer Link
City or Country
Taipei, Taiwan
Citation
LIN, Shang-Wei; ANDRÉ, Étienne; DONG, Jin Song; SUN, Jun; and LIU, Yang.
An efficient algorithm for learning event-recording automata. (2011). Proceedings of the 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14. 463-472.
Available at: https://ink.library.smu.edu.sg/sis_research/5026
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/978-3-642-24372-1_35