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

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    26 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Title of host publicationGrammatical Inference: Theoretical Results and Applications (10th International Colloquium, ICGI 2010, Valencia, Spain, September 13-16, 2010. Proceedings)
    EditorsJ.M. Sempere, P. Garciá
    Place of PublicationBerlin
    PublisherSpringer
    Pages203-216
    ISBN (Print)978-3-642-15487-4
    DOIs
    Publication statusPublished - 2010

    Publication series

    NameLecture Notes in Computer Science
    Volume6339
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'A likelihood-ratio test for identifying probabilistic deterministic real-time automata from positive data'. Together they form a unique fingerprint.

    Cite this