Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Correctness and Performance of an Incremental Learning Algorithm for Finite Automata
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-9706-5008
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2010 (English)Report (Other academic)
Abstract [en]

We present a new algorithm IDSfor incremental learning of deterministic finite automata (DFA). This algorithm is based on the concept of distinguishing sequences introduced in [Angluin 1981]. We give a rigorous proof that two versions of this learning algorithm correctly learn in the limit. Finally we present an empirical performance analysis that compares these two algorithms, focussing on learning times and different types of learning queries. We conclude that IDSis an efficient algorithm for software engineering applications of automata learning, such as testing and model inference.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology , 2010. , 19 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-37678OAI: oai:DiVA.org:kth-37678DiVA: diva2:434775
Note
QC 20110816Available from: 2011-08-16 Created: 2011-08-16 Last updated: 2011-08-22Bibliographically approved
In thesis
1. Incremental Learning and Testing of Reactive Systems
Open this publication in new window or tab >>Incremental Learning and Testing of Reactive Systems
2011 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis concerns the design, implementation and evaluation of a specification based testing architecture for reactive systems using the paradigm of learning-based testing. As part of this work we have designed, verified and implemented new incremental learning algorithms for DFA and Kripke structures.These have been integrated with the NuSMV model checker to give a new learning-based testing architecture. We have evaluated our architecture on case studies and shown that the method is effective.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2011. x, 45 p.
Series
Trita-CSC-A, ISSN 1653-5723 ; 2011:14
Keyword
Incremental learning, software testing, specification based testing, reactive systems, model checking
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-37763 (URN)978-91-7501-062-5 (ISBN)
Presentation
2011-09-30, K2, Teknikringen 28, KTH, Stockholm, 10:00 (English)
Opponent
Supervisors
Note
QC 20110822Available from: 2011-08-22 Created: 2011-08-17 Last updated: 2011-08-22Bibliographically approved

Open Access in DiVA

fulltext(473 kB)257 downloads
File information
File name FULLTEXT01.pdfFile size 473 kBChecksum SHA-512
b7fc0377fcc6938ba328c66f0dd2916b9c25d3442698d53618da90176623bb816ea1d2aa06efa31e8981590039d1542bc22f98d58d32e55ad1d960cda434838e
Type fulltextMimetype application/pdf

Authority records BETA

Meinke, Karl

Search in DiVA

By author/editor
Meinke, KarlSindhu, Muddassar
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 257 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 204 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf