Minimal Separating Sequences for All Pairs of States

Rick Smetsers, Joshua Moerman, David N. Jansen

Research output: Chapter in Book/Report/Conference proceedingConference Article in proceedingAcademicpeer-review


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 languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
EditorsAdrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, Bianca Truthe
Number of pages13
ISBN (Electronic) 978-3-319-30000-9
ISBN (Print)978-3-319-29999-0
Publication statusPublished - 2016
Externally publishedYes
Event10th International Conference of Language and Automata Theory and Applications - Prague, Czech Republic
Duration: 14 Mar 201618 Mar 2016
Conference number: 10

Publication series

SeriesTheoretical Computer Science and General Issues (LNCS subseries)
SeriesLecture Notes in Computer Science


Conference10th International Conference of Language and Automata Theory and Applications
Abbreviated titleLATA
Country/TerritoryCzech Republic
Internet address


Dive into the research topics of 'Minimal Separating Sequences for All Pairs of States'. Together they form a unique fingerprint.

Cite this