Cho, Da-Jung, Goč, Daniel 
ORCID: 0000-0002-8265-4918, Han, Yo-Sub, Ko, Sang-Ki, Palioudakis, Alexandros ORCID: 0000-0003-3181-6072 and Salomaa, Kai
(2017)
State complexity of permutation on finite languages over a binary alphabet.
Theoretical Computer Science, 682.
pp. 67-78.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
SCpermutation.pdf - Author Accepted Manuscript Download (155kB) |
Abstract
The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with [formula presented] states. We show that if the language consists of equal length binary strings the bound can be improved to f(n)=[formula presented] and for every n congruent to 1 modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L(A) needs f(n) states.
| Item Type: | Article |
|---|---|
| Depositing User: | Symplectic Admin |
| Date Deposited: | 24 Apr 2017 06:46 |
| Last Modified: | 19 Jan 2023 07:05 |
| DOI: | 10.1016/j.tcs.2017.03.007 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007078 |
Dimensions
Dimensions
