An efficient algorithm for learning event-recording automata

• Main Authors: LIN, Shang-Wei, ANDRÉ, Étienne, DONG, Jin Song, SUN, Jun, LIU, Yang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2011
• Subjects: Programming Languages and Compilers; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/5026; https://ink.library.smu.edu.sg/context/sis_research/article/6029/viewcontent/An_Efficient_Algorithm_for_Learning_Event_Recording_Automata.pdf
• Institution: Singapore Management University

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.