State complexity of k-union and k-intersection for prefix-free regular languages

Hae Sung Eom; Yo Sub Han; Kai Salomaa

doi:10.1007/978-3-642-39310-5_9

State complexity of k-union and k-intersection for prefix-free regular languages

Hae Sung Eom, Yo Sub Han, Kai Salomaa

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

We investigate the state complexity of multiple unions and of multiple intersections for prefix-free regular languages. Prefix-free deterministic finite automata have their own unique structural properties that are crucial for obtaining state complexity upper bounds that are improved from those for general regular languages. We present a tight lower bound construction for k-union using an alphabet of size k + 1 and for k-intersection using a binary alphabet. We prove that the state complexity upper bound for k-union cannot be reached by languages over an alphabet with less than k symbols. We also give a lower bound construction for k-union using a binary alphabet that is within a constant factor of the upper bound.

Original language	English
Title of host publication	Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings
Pages	78-89
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-39310-5_9
Publication status	Published - 2013
Event	15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013 - London, ON, Canada Duration: 2013 Jul 22 → 2013 Jul 25

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8031 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013
Country/Territory	Canada
City	London, ON
Period	13/7/22 → 13/7/25

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-39310-5_9

Cite this

Eom, H. S., Han, Y. S., & Salomaa, K. (2013). State complexity of k-union and k-intersection for prefix-free regular languages. In Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings (pp. 78-89). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8031 LNCS). https://doi.org/10.1007/978-3-642-39310-5_9

Eom, Hae Sung ; Han, Yo Sub ; Salomaa, Kai. / State complexity of k-union and k-intersection for prefix-free regular languages. Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings. 2013. pp. 78-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3dd6278b3dbd45d283084e3a4c8c2fbb,

title = "State complexity of k-union and k-intersection for prefix-free regular languages",

abstract = "We investigate the state complexity of multiple unions and of multiple intersections for prefix-free regular languages. Prefix-free deterministic finite automata have their own unique structural properties that are crucial for obtaining state complexity upper bounds that are improved from those for general regular languages. We present a tight lower bound construction for k-union using an alphabet of size k + 1 and for k-intersection using a binary alphabet. We prove that the state complexity upper bound for k-union cannot be reached by languages over an alphabet with less than k symbols. We also give a lower bound construction for k-union using a binary alphabet that is within a constant factor of the upper bound.",

author = "Eom, {Hae Sung} and Han, {Yo Sub} and Kai Salomaa",

year = "2013",

doi = "10.1007/978-3-642-39310-5_9",

language = "English",

isbn = "9783642393099",

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

pages = "78--89",

booktitle = "Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings",

note = "15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013 ; Conference date: 22-07-2013 Through 25-07-2013",

}

Eom, HS, Han, YS & Salomaa, K 2013, State complexity of k-union and k-intersection for prefix-free regular languages. in Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8031 LNCS, pp. 78-89, 15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013, London, ON, Canada, 13/7/22. https://doi.org/10.1007/978-3-642-39310-5_9

State complexity of k-union and k-intersection for prefix-free regular languages. / Eom, Hae Sung; Han, Yo Sub; Salomaa, Kai.
Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings. 2013. p. 78-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8031 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - State complexity of k-union and k-intersection for prefix-free regular languages

AU - Eom, Hae Sung

AU - Han, Yo Sub

AU - Salomaa, Kai

PY - 2013

Y1 - 2013

N2 - We investigate the state complexity of multiple unions and of multiple intersections for prefix-free regular languages. Prefix-free deterministic finite automata have their own unique structural properties that are crucial for obtaining state complexity upper bounds that are improved from those for general regular languages. We present a tight lower bound construction for k-union using an alphabet of size k + 1 and for k-intersection using a binary alphabet. We prove that the state complexity upper bound for k-union cannot be reached by languages over an alphabet with less than k symbols. We also give a lower bound construction for k-union using a binary alphabet that is within a constant factor of the upper bound.

AB - We investigate the state complexity of multiple unions and of multiple intersections for prefix-free regular languages. Prefix-free deterministic finite automata have their own unique structural properties that are crucial for obtaining state complexity upper bounds that are improved from those for general regular languages. We present a tight lower bound construction for k-union using an alphabet of size k + 1 and for k-intersection using a binary alphabet. We prove that the state complexity upper bound for k-union cannot be reached by languages over an alphabet with less than k symbols. We also give a lower bound construction for k-union using a binary alphabet that is within a constant factor of the upper bound.

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

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

U2 - 10.1007/978-3-642-39310-5_9

DO - 10.1007/978-3-642-39310-5_9

M3 - Conference contribution

AN - SCOPUS:84884475434

SN - 9783642393099

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 78

EP - 89

BT - Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings

T2 - 15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013

Y2 - 22 July 2013 through 25 July 2013

ER -

Eom HS, Han YS, Salomaa K. State complexity of k-union and k-intersection for prefix-free regular languages. In Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings. 2013. p. 78-89. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-39310-5_9

State complexity of k-union and k-intersection for prefix-free regular languages

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this