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

College of Computing

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

6 Citations (Scopus)

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
Publication status	Published - 2017 Jun 19

Bibliographical note

Funding Information:
Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002). Goč, Palioudakis and Salomaa were supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

Publisher Copyright:
© 2017 Elsevier B.V.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2017.03.007

Cite this

@article{26722a9ec7a74d8699c3b4574d5233ed,

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

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

note = "Funding Information: Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002). Go{\v c}, Palioudakis and Salomaa were supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. 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",

}

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

N1 - Funding Information: Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002). Goč, Palioudakis and Salomaa were supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: © 2017 Elsevier B.V.

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.

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

UR - http://www.scopus.com/inward/citedby.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

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this