Minimal Separating Sequences for All Pairs of States

Rick Smetsers; Joshua Moerman; David N. Jansen

doi:10.1007/978-3-319-30000-9_14

Minimal Separating Sequences for All Pairs of States

Rick Smetsers, Joshua Moerman, David N. Jansen

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

Abstract

Finding minimal separating sequences for all pairs of inequivalent states in a finite state machine is a classic problem in automata theory. Sets of minimal separating sequences, for instance, play a central role in many conformance testing methods. Moore has already outlined a partition refinement algorithm that constructs such a set of sequences in O(mn) time, where m is the number of transitions and n is the number of states. In this paper, we present an improved algorithm based on the minimization algorithm of Hopcroft that runs in O(mlogn) time. The efficiency of our algorithm is empirically verified and compared to the traditional algorithm.

Original language	English
Title of host publication	Language and Automata Theory and Applications
Subtitle of host publication	10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
Editors	Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, Bianca Truthe
Publisher	Springer
Pages	181-193
Number of pages	13
ISBN (Electronic)	978-3-319-30000-9
ISBN (Print)	978-3-319-29999-0
DOIs	https://doi.org/10.1007/978-3-319-30000-9_14
Publication status	Published - 2016
Externally published	Yes
Event	10th International Conference of Language and Automata Theory and Applications - Prague, Czech Republic Duration: 14 Mar 2016 → 18 Mar 2016 Conference number: 10 https://link.springer.com/book/10.1007/978-3-319-30000-9

Publication series

Series	Theoretical Computer Science and General Issues (LNCS subseries)
Volume	9618

Series	Lecture Notes in Computer Science
Volume	9618
ISSN	0302-9743

Conference

Conference	10th International Conference of Language and Automata Theory and Applications
Abbreviated title	LATA
Country/Territory	Czech Republic
City	Prague
Period	14/03/16 → 18/03/16
Internet address	https://link.springer.com/book/10.1007/978-3-319-30000-9

Access to Document

10.1007/978-3-319-30000-9_14

Cite this

Smetsers, R., Moerman, J., & Jansen, D. N. (2016). Minimal Separating Sequences for All Pairs of States. In A.-H. Dediu, J. Janoušek, C. Martín-Vide, & B. Truthe (Eds.), Language and Automata Theory and Applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings (pp. 181-193). Springer. https://doi.org/10.1007/978-3-319-30000-9_14

Smetsers, Rick ; Moerman, Joshua ; Jansen, David N. / Minimal Separating Sequences for All Pairs of States. Language and Automata Theory and Applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. editor / Adrian-Horia Dediu ; Jan Janoušek ; Carlos Martín-Vide ; Bianca Truthe. Springer, 2016. pp. 181-193 (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 9618). (Lecture Notes in Computer Science, Vol. 9618).

@inproceedings{91afb87c316646a3a3a8918daf21574f,

title = "Minimal Separating Sequences for All Pairs of States",

abstract = "Finding minimal separating sequences for all pairs of inequivalent states in a finite state machine is a classic problem in automata theory. Sets of minimal separating sequences, for instance, play a central role in many conformance testing methods. Moore has already outlined a partition refinement algorithm that constructs such a set of sequences in O(mn) time, where m is the number of transitions and n is the number of states. In this paper, we present an improved algorithm based on the minimization algorithm of Hopcroft that runs in O(mlogn) time. The efficiency of our algorithm is empirically verified and compared to the traditional algorithm.",

author = "Rick Smetsers and Joshua Moerman and Jansen, {David N.}",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; 10th International Conference of Language and Automata Theory and Applications, LATA ; Conference date: 14-03-2016 Through 18-03-2016",

year = "2016",

doi = "10.1007/978-3-319-30000-9_14",

language = "English",

isbn = "978-3-319-29999-0",

series = "Theoretical Computer Science and General Issues (LNCS subseries)",

publisher = "Springer",

pages = "181--193",

editor = "Adrian-Horia Dediu and Jan Janou{\v s}ek and Carlos Mart{\'i}n-Vide and Bianca Truthe",

booktitle = "Language and Automata Theory and Applications",

url = "https://link.springer.com/book/10.1007/978-3-319-30000-9",

}

Smetsers, R, Moerman, J & Jansen, DN 2016, Minimal Separating Sequences for All Pairs of States. in A-H Dediu, J Janoušek, C Martín-Vide & B Truthe (eds), Language and Automata Theory and Applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. Springer, Theoretical Computer Science and General Issues (LNCS subseries), vol. 9618, Lecture Notes in Computer Science, vol. 9618, pp. 181-193, 10th International Conference of Language and Automata Theory and Applications, Prague, Czech Republic, 14/03/16. https://doi.org/10.1007/978-3-319-30000-9_14

Minimal Separating Sequences for All Pairs of States. / Smetsers, Rick; Moerman, Joshua; Jansen, David N.
Language and Automata Theory and Applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. ed. / Adrian-Horia Dediu; Jan Janoušek; Carlos Martín-Vide; Bianca Truthe. Springer, 2016. p. 181-193 (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 9618). (Lecture Notes in Computer Science, Vol. 9618).

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

TY - GEN

T1 - Minimal Separating Sequences for All Pairs of States

AU - Smetsers, Rick

AU - Moerman, Joshua

AU - Jansen, David N.

N1 - Conference code: 10

PY - 2016

Y1 - 2016

N2 - Finding minimal separating sequences for all pairs of inequivalent states in a finite state machine is a classic problem in automata theory. Sets of minimal separating sequences, for instance, play a central role in many conformance testing methods. Moore has already outlined a partition refinement algorithm that constructs such a set of sequences in O(mn) time, where m is the number of transitions and n is the number of states. In this paper, we present an improved algorithm based on the minimization algorithm of Hopcroft that runs in O(mlogn) time. The efficiency of our algorithm is empirically verified and compared to the traditional algorithm.

AB - Finding minimal separating sequences for all pairs of inequivalent states in a finite state machine is a classic problem in automata theory. Sets of minimal separating sequences, for instance, play a central role in many conformance testing methods. Moore has already outlined a partition refinement algorithm that constructs such a set of sequences in O(mn) time, where m is the number of transitions and n is the number of states. In this paper, we present an improved algorithm based on the minimization algorithm of Hopcroft that runs in O(mlogn) time. The efficiency of our algorithm is empirically verified and compared to the traditional algorithm.

U2 - 10.1007/978-3-319-30000-9_14

DO - 10.1007/978-3-319-30000-9_14

M3 - Conference Article in proceeding

SN - 978-3-319-29999-0

T3 - Theoretical Computer Science and General Issues (LNCS subseries)

SP - 181

EP - 193

BT - Language and Automata Theory and Applications

A2 - Dediu, Adrian-Horia

A2 - Janoušek, Jan

A2 - Martín-Vide, Carlos

A2 - Truthe, Bianca

PB - Springer

T2 - 10th International Conference of Language and Automata Theory and Applications

Y2 - 14 March 2016 through 18 March 2016

ER -

Smetsers R, Moerman J, Jansen DN. Minimal Separating Sequences for All Pairs of States. In Dediu AH, Janoušek J, Martín-Vide C, Truthe B, editors, Language and Automata Theory and Applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. Springer. 2016. p. 181-193. (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 9618). (Lecture Notes in Computer Science, Vol. 9618). doi: 10.1007/978-3-319-30000-9_14

Minimal Separating Sequences for All Pairs of States

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this