Dupont, Pierre
[UCL]
Lambeau, Bernard
[UCL]
Damas, Christophe
[UCL]
van Lamsweerde, Axel
[UCL]
This article presents a novel application of grammatical inference techniques to the synthesis of behavior models of software systems. This synthesis is used for the elicitation of software requirements. This problem is formulated as a deterministic finite-state automaton induction problem from positive and negative scenarios provided by an end user of the software-to-be. A query-driven state merging (QSM) algorithm is proposed. It extends the Regular Positive and Negative Inference (RPNI) and blue-fringe algorithms by allowing membership queries to be submitted to the end user. State merging operations can be further constrained by some prior domain knowledge formulated as fluents, goals, domain properties, and models of external software components. The incorporation of domain knowledge both reduces the number of queries and guarantees that the induced model is consistent with such knowledge. The proposed techniques are implemented in the ISIS tool and practical evaluations on standard requirements engineering test cases and synthetic data illustrate the interest of this approach.
- Angluin Dana, On the complexity of minimum inference of regular sets, 10.1016/s0019-9958(78)90683-6
- Angluin Dana, A note on the number of queries needed to identify regular languages, 10.1016/s0019-9958(81)90090-5
- Angluin Dana, Learning regular sets from queries and counterexamples, 10.1016/0890-5401(87)90052-6
- Bell , T. and T. Thayer . 1976 . Software requirements: Are they really a problem? In: 2nd International Conference on Software Enginering (ICSE) , pp. 61 – 68 . San Francisco , CA .
- Boehm B., Software Engineering Economics (1981)
- Brooks F., IEEE Computer, 20, 10 (1987)
- Coste François, Fredouille Daniel, Kermorvant Christopher, de la Higuera Colin, Introducing Domain and Typing Bias in Automata Inference, Grammatical Inference: Algorithms and Applications (2004) ISBN:9783540234104 p.115-126, 10.1007/978-3-540-30195-0_11
- Coste François, Nicolas Jacques, How considering incompatible state mergings may reduce the DFA induction search tree, Grammatical Inference (1998) ISBN:9783540647768 p.199-210, 10.1007/bfb0054076
- Damas C., Lambeau B., Dupont P., van Lamsweerde A., Generating annotated behavior models from end-user scenarios, 10.1109/tse.2005.138
- Damas , C. , B. Lambeau , and A. van Lamsweerde . 2006 . Scenarios, goals, and state machines: A win–win partnership for model synthesis . International ACM Symposium on the Foundations of Software Engineering , pp. 197 – 207 . Portland , OR .
- Dupont Pierre, Incremental regular inference, Grammatical Interference: Learning Syntax from Sentences (1996) ISBN:9783540617785 p.222-237, 10.1007/bfb0033357
- Dupont P., Miclet L., Vidal E., What is the search space of the regular inference?, Grammatical Inference and Applications (1994) ISBN:9783540584735 p.25-37, 10.1007/3-540-58473-0_134
- Giannakopoulou , D. and J. Magee . 2003 . Fluent model checking for event-based systems . In: 9th European Software Engineering Conference/11th ACM SIGSOFT International Symposium on Foundations of Software Engineering , pp. 257 – 266 . Helsinki .
- Gold E Mark, Complexity of automaton identification from given data, 10.1016/s0019-9958(78)90562-4
- Hall , R. and A. Zisman . 2004 . Omml: A behavioral model interchange format . In: 12th IEEE Joint International Requirements Engineering Conference , pp. 272 – 282 , Kyoto , Japan.
- Hopcroft J., Introduction to Automata Theory, Languages and Computation (1979)
- Joseph M., Real-Time Systems: Specification, Verification and Analysis (1996)
- Kruger I., International Workshop on Distributed and Parallel Emebedded Systems, 61 (1998)
- Lang , K. 1992 . Random DFA's can be approximately learned from sparse uniform examples . In: 5th ACM Workshop on Computational Learning Theory , pp. 45 – 52 , Pittsburgh , PA , USA .
- Lang Kevin J., Pearlmutter Barak A., Price Rodney A., Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm, Grammatical Inference (1998) ISBN:9783540647768 p.1-12, 10.1007/bfb0054059
- Magee J., Concurrency: State Models and Java Programs (1999)
- Mäkinen , E. and T. Systä . 2001 . Mas – an interactive synthetiser to support behavorial modeling in UML . In: 27th International Conference on Software Engineering , pp. 15 – 24 , Toronto , Canada .
- Oncina J., García P., INFERRING REGULAR LANGUAGES IN POLYNOMIAL UPDATED TIME, Series in Machine Perception and Artificial Intelligence (1992) ISBN:9789810208813 p.49-61, 10.1142/9789812797902_0004
- Oncina J., Garcia P., Vidal E., Learning subsequential transducers for pattern recognition interpretation tasks, 10.1109/34.211465
- The Standish Group . 1995 . Software chaos . http://www.standishgroup.com. Last accessed 21 January 2008 .
- Uchitel S., Kramer J., Magee J., Synthesis of behavioral models from scenarios, 10.1109/tse.2003.1178048
- Valiant L. G., A theory of the learnable, 10.1145/1968.1972
- van Lamsweerde , A. 2001 . Goal-oriented requirements engineering: A guided tour . In: 5th Intl. Symp. Requirements Engineering (RE) , pp. 249 – 263 . Toronto : IEEE Press .
- van Lamsweerde , A. 2004 . Goal-oriented requirements engineering: A roundtrip from research to practice . In: 12th IEEE Joint International Requirements Engineering Conference , pp. 4 – 7 , Kyoto , Japan .
- van Lamsweerde A., Willemet L., Inferring declarative requirements specifications from operational scenarios, 10.1109/32.738341
- Whittle , J. and J. Schumann . 2000 . Generating statechart designs from scenarios . In: 22nd International Conference on Software Engineering , pp. 314 – 323 . Limerick , Ireland .
Bibliographic reference |
Dupont, Pierre ; Lambeau, Bernard ; Damas, Christophe ; van Lamsweerde, Axel. The QSM algorithm and its application to software behavior model induction. In: Applied Artificial Intelligence : an international journal, Vol. 22, no. 1-2, p. 77-115 (2008) |
Permanent URL |
http://hdl.handle.net/2078.1/36781 |