Abstract | ||
---|---|---|
We present an algorithm for inferring a timed-automaton model of a system from information obtained by observing its external behavior. Since timed automata can not in general be determinized, we restrict our attention to systems that can be described by deterministic event-recording automata. In previous work we have presented algorithms for event-recording automata that satisfy the restriction that there is at most one transition per alphabet symbol from each state. This restriction was lifted in subsequent work by an algorithm based on the region graph. In this paper, we extend previous work by considering the full class of event-recording automata, while still avoiding to base it on the (usually prohibitively large) region graph. Our construction deviates from previous work on inference of automata in that it first constructs a so called timed decision tree from observations of system behavior, which is thereafter folded into an automaton. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11817949_29 | CONCUR |
Keywords | Field | DocType |
external behavior,alphabet symbol,event-recording automaton,region graph,construction deviate,subsequent work,decision tree,deterministic event-recording automaton,system behavior,previous work,regular language,deterministic finite automaton | Quantum finite automata,Automata theory,Continuous spatial automaton,Deterministic automaton,Mobile automaton,Nested word,Computer science,Algorithm,Theoretical computer science,Timed automaton,ω-automaton | Conference |
Volume | ISSN | ISBN |
4137 | 0302-9743 | 3-540-37376-4 |
Citations | PageRank | References |
22 | 0.85 | 27 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Olga Grinchtein | 1 | 115 | 7.91 |
bengt jonsson | 2 | 3637 | 263.46 |
Paul Pettersson | 3 | 2636 | 174.89 |