Please use this identifier to cite or link to this item:
|Title:||An efficient algorithm for learning event-recording automata||Authors:||Lin, S.-W.
|Issue Date:||2011||Citation:||Lin, S.-W.,André, É.,Dong, J.S.,Sun, J.,Liu, Y. (2011). An efficient algorithm for learning event-recording automata. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6996 LNCS : 463-472. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-24372-1_35||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. © 2011 Springer-Verlag.||Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||URI:||http://scholarbank.nus.edu.sg/handle/10635/43170||ISBN:||9783642243714||ISSN:||03029743||DOI:||10.1007/978-3-642-24372-1_35|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 23, 2019
checked on May 22, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.