A likelihood-ratio test for identifying probabilistic deterministic real-time automata from positive data

S.E. Verwer, M. Weerdt, de, C. Witteveen

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

26 Citaten (Scopus)

Samenvatting

We adapt an algorithm (RTI) for identifying (learning) a deterministic real-time automaton (DRTA) to the setting of positive timed strings (or time-stamped event sequences). An DRTA can be seen as a deterministic finite state automaton (DFA) with time constraints. Because DRTAs model time using numbers, they can be exponentially more compact than equivalent DFA models that model time using states. We use a new likelihood-ratio statistical test for checking consistency in the RTI algorithm. The result is the RTI¿+ algorithm, which stands for real-time identification from positive data. RTI¿+ is an efficient algorithm for identifying DRTAs from positive data. We show using artificial data that RTI¿+ is capable of identifying sufficiently large DRTAs in order to identify real-world real-time systems.
Originele taal-2Engels
TitelGrammatical Inference: Theoretical Results and Applications (10th International Colloquium, ICGI 2010, Valencia, Spain, September 13-16, 2010. Proceedings)
RedacteurenJ.M. Sempere, P. Garciá
Plaats van productieBerlin
UitgeverijSpringer
Pagina's203-216
ISBN van geprinte versie978-3-642-15487-4
DOI's
StatusGepubliceerd - 2010

Publicatie series

NaamLecture Notes in Computer Science
Volume6339
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'A likelihood-ratio test for identifying probabilistic deterministic real-time automata from positive data'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Verwer, S. E., Weerdt, de, M., & Witteveen, C. (2010). A likelihood-ratio test for identifying probabilistic deterministic real-time automata from positive data. In J. M. Sempere, & P. Garciá (editors), Grammatical Inference: Theoretical Results and Applications (10th International Colloquium, ICGI 2010, Valencia, Spain, September 13-16, 2010. Proceedings) (blz. 203-216). (Lecture Notes in Computer Science; Vol. 6339). Springer. https://doi.org/10.1007/978-3-642-15488-1_17