State complexity of permutation on finite languages over a binary alphabet
| Autor: | Da Jung Cho, Yo-Sub Han, Daniel Goc, Kai Salomaa, Sang-Ki Ko, Alexandros Palioudakis |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Permutation (music) Finite-state machine General Computer Science Modulo String (computer science) Bit-reversal permutation 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Set (abstract data type) Deterministic finite automaton DFA minimization 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Theoretical Computer Science |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2017.03.007 |
| Popis: | 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 n 2 − n + 2 2 states. We show that if the language consists of equal length binary strings the bound can be improved to f ( n ) = n 2 + n + 1 3 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect