Editing Permutation automaton (section)

== Applications ==
The pure-group languages were the first interesting family of [[regular languages]] for which the [[star height problem]] was proved to be [[computable]].<ref name=McNaughton1967 /><ref name="Brzozowski80">[[Janusz Brzozowski (computer scientist)|Janusz A. Brzozowski]]: ''Open problems about regular languages'', In: Ronald V. Book, editor, ''Formal language theory—Perspectives and open problems'', pp.&nbsp;23–47. Academic Press, 1980 [https://www.cs.uwaterloo.ca/research/tr/1980/CS-80-03.pdf (technical report version)]</ref>

Another mathematical problem on regular languages is the ''separating words problem'', which asks for the size of a smallest deterministic finite automaton that distinguishes between two given words of length at most ''n'' &ndash; by accepting one word and rejecting the other. The known upper bound in the general case is <math>O(n^{2/5}(\log n)^{3/5})</math>.<ref>{{Cite book | last1 = Demaine | first1 = E. D.| author-link1 = Erik Demaine| last2 = Eisenstat | first2 = S. | last3 = Shallit | first3 = J.| author-link3 = Jeffrey Shallit| last4 = Wilson | first4 = D. A.| chapter = Remarks on Separating Words | doi = 10.1007/978-3-642-22600-7_12 | title = [[Descriptional Complexity of Formal Systems]]| series = Lecture Notes in Computer Science | volume = 6808 | pages = 147–157| year = 2011 | isbn = 978-3-642-22599-4 }}</ref> The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to <math>O(n^{1/2})</math>.<ref>{{Citation
 | author = J. M. Robson
 | title = Separating words with machines and groups
 | url = http://www.numdam.org/item?id=ITA_1996__30_1_81_0
 | year = 1996
 | journal = RAIRO &ndash; Informatique théorique et applications
 | pages = 81–86
 | volume = 30
 | issue = 1
 | access-date = 2012-07-15
}}</ref>