Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-24372-1_35
Title: An efficient algorithm for learning event-recording automata
Authors: Lin, S.-W. 
André, É. 
Dong, J.S. 
Sun, J.
Liu, Y. 
Issue Date: 2011
Source: 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.

SCOPUSTM   
Citations

7
checked on Dec 13, 2017

Page view(s)

56
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.