| 1. |
- Berg, Therese, et al.
(författare)
-
Insights to Angluin's Learning
- 2005
-
Ingår i: Electr. Notes on Theoret. Comput. Sci.. ; 118, s. 3-18
-
Tidskriftsartikel (refereegranskat)
|
|
| 2. |
- Berg, Therese, et al.
(författare)
-
Insights to Angluin's Learning
- 2005
-
Ingår i: Electronic Notes in Theoretical Computer Science. - : Elsevier BV. - 1571-0661. ; 118, s. 3-18
-
Tidskriftsartikel (refereegranskat)abstract
- Among other domains, learning finite-state machines is important for obtaining a model of a system under development, so that powerful formal methods such as model checking can be applied. A prominent algorithm for learning such devices was developed by Angluin. We have implemented this algorithm in a straightforward way to gain further insights to practical applicability. Furthermore, we have analyzed its performance on randomly generated as well as real-world examples. Our experiments focus on the impact of the alphabet size and the number of states on the needed number of membership queries. Additionally, we have implemented and analyzed an optimized version for learning prefix-closed regular languages. Memory consumption is one major obstacle when we attempted to learn large examples. We see that prefix-closed languages are relatively hard to learn compared to arbitrary regular languages. The optimization, however, shows positive results.
|
|
| 3. |
|
|
| 4. |
- Grinchtein, Olga, et al.
(författare)
-
Inference of Timed Transition Systems
- 2005
-
Ingår i: Proceedings of the 6th International Workshop on Verification of Infinite-State Systems (INFINITY).
-
Konferensbidrag (refereegranskat)
|
|
| 5. |
- Grinchtein, Olga, et al.
(författare)
-
Learning of Event-Recording Automata
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In regular inference, a regular language is inferred from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. One of the most well-known regular inference algorithms is the L* algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We extend Angluin's algorithm for on-line learning of regular languages to the setting of timed systems. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by deterministic event-recording automata (DERAs). We present three algorithms, TLsg*, TLnsg* and TLs*, for inference of DERAs. In TLsg* and TLnsg*, we further restrict event-recording automata to be event-deterministic in the sense that each state has at most one outgoing transition per action; learning such an automaton becomes significantly more tractable. The algorithm TLnsg* builds on TLsg*, by attempts to construct a smaller (in number of locations) automaton. Finally, TLs* is a learning algorithm for a full class of deterministic event-recording automata, which infers a so called simple DERA, which is similar in spirit to the region graph.
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
|
|
| 9. |
|
|
| 10. |
- Pretschner, Alexander, et al.
(författare)
-
Model-Based Testing - A Glossary
- 2005
-
Ingår i: Model-Based Testing of Reactive Systems. - : Springer. - 3540262784 ; , s. 607-609
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
