2010 | OriginalPaper | Buchkapitel
A Likelihood-Ratio Test for Identifying Probabilistic Deterministic Real-Time Automata from Positive Data
verfasst von : Sicco Verwer, Mathijs de Weerdt, Cees Witteveen
Erschienen in: Grammatical Inference: Theoretical Results and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.