State complexity of permutation on finite languages over a binary alphabet

Da Jung Cho; Daniel Goč; Yo Sub Han; Sang Ki Ko; Alexandros Palioudakis; Kai Salomaa

doi:10.1016/j.tcs.2017.03.007

State complexity of permutation on finite languages over a binary alphabet

Da Jung Cho, Daniel Goč, Yo Sub Han, Sang Ki Ko, Alexandros Palioudakis, Kai Salomaa

Department of Artificial Intelligence

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

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.

Original language	English
Pages (from-to)	67-78
Number of pages	12
Journal	Theoretical Computer Science
Volume	682
DOIs	https://doi.org/10.1016/j.tcs.2017.03.007
State	Published - 19 Jun 2017

Keywords

Finite automata
Finite languages
Parikh equivalence
State complexity

Access to Document

10.1016/j.tcs.2017.03.007

Cite this

@article{bb108a56548845a0a629316a5bcb18d2,

title = "State complexity of permutation on finite languages over a binary alphabet",

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.",

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

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

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = jun,

day = "19",

doi = "10.1016/j.tcs.2017.03.007",

language = "English",

volume = "682",

pages = "67--78",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - State complexity of permutation on finite languages over a binary alphabet

AU - Cho, Da Jung

AU - Goč, Daniel

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Palioudakis, Alexandros

AU - Salomaa, Kai

PY - 2017/6/19

Y1 - 2017/6/19

N2 - 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.

AB - 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.

KW - Finite automata

KW - Finite languages

KW - Parikh equivalence

KW - State complexity

UR - http://www.scopus.com/inward/record.url?scp=85017111531&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2017.03.007

DO - 10.1016/j.tcs.2017.03.007

M3 - Article

AN - SCOPUS:85017111531

SN - 0304-3975

VL - 682

SP - 67

EP - 78

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

State complexity of permutation on finite languages over a binary alphabet

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this