@inproceedings{3fd1b86a1d36490d9f7e6df2ce543685,

title = "The state complexity of permutations on finite languages over binary alphabets",

abstract = "We investigate the state complexity of the permutation operation over finite binary languages. We first give an upper bound of the state complexity of the permutation operation for a restricted case of these languages. We later present a general upper bound of the state complexity of permutation over finite binary languages, which is asymptotically the same as the previous case. Moreover, we show that there is a family of languages that the minimal DFA recognizing each of these languages needs at least as many states as the given upper bound for the restricted case. Furthermore, we investigate the state complexity of permutation by focusing on the structure of the minimal DFA.",

keywords = "Finite automata, Finite languages, Parikh equivalence, Permutation, State complexity",

author = "Alexandros Palioudakis and Cho, {Da Jung} and Daniel Go{\v c} and Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 17th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2015 ; Conference date: 25-06-2015 Through 27-06-2015",

year = "2015",

doi = "10.1007/978-3-319-19225-3_19",

language = "English",

isbn = "9783319192246",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "220--230",

editor = "Alexander Okhotin and Jeffrey Shallit",

booktitle = "Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Proceedings",

address = "Germany",

}