State complexity of deletion

Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-319-09698-8_4

State complexity of deletion

Yo Sub Han, Sang Ki Ko, Kai Salomaa

Department of Artificial Intelligence

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

Abstract

It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is n ·2 ^n-1 (respectively,) when using complete (respectively, incomplete) deterministic finite automata.

Original language	English
Title of host publication	Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings
Publisher	Springer Verlag
Pages	37-48
Number of pages	12
ISBN (Print)	9783319096971
DOIs	https://doi.org/10.1007/978-3-319-09698-8_4
State	Published - 2014
Event	18th International Conference on Developments in Language Theory, DLT 2014 - Ekaterinburg, Russian Federation Duration: 26 Aug 2014 → 29 Aug 2014

Publication series

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

Conference

Conference	18th International Conference on Developments in Language Theory, DLT 2014
Country/Territory	Russian Federation
City	Ekaterinburg
Period	26/08/14 → 29/08/14

Access to Document

10.1007/978-3-319-09698-8_4

Cite this

Han, Y. S., Ko, S. K., & Salomaa, K. (2014). State complexity of deletion. In Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings (pp. 37-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8633 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-09698-8_4

@inproceedings{0879f105ae9942319170e253daeb2e46,

title = "State complexity of deletion",

abstract = "It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is n ·2 n-1 (respectively,) when using complete (respectively, incomplete) deterministic finite automata.",

author = "Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

year = "2014",

doi = "10.1007/978-3-319-09698-8_4",

language = "English",

isbn = "9783319096971",

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

publisher = "Springer Verlag",

pages = "37--48",

booktitle = "Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings",

address = "Germany",

note = "18th International Conference on Developments in Language Theory, DLT 2014 ; Conference date: 26-08-2014 Through 29-08-2014",

}

Han, YS, Ko, SK & Salomaa, K 2014, State complexity of deletion. in Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8633 LNCS, Springer Verlag, pp. 37-48, 18th International Conference on Developments in Language Theory, DLT 2014, Ekaterinburg, Russian Federation, 26/08/14. https://doi.org/10.1007/978-3-319-09698-8_4

State complexity of deletion. / Han, Yo Sub; Ko, Sang Ki; Salomaa, Kai.
Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings. Springer Verlag, 2014. p. 37-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8633 LNCS).

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

TY - GEN

T1 - State complexity of deletion

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2014

Y1 - 2014

N2 - It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is n ·2 n-1 (respectively,) when using complete (respectively, incomplete) deterministic finite automata.

AB - It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is n ·2 n-1 (respectively,) when using complete (respectively, incomplete) deterministic finite automata.

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

U2 - 10.1007/978-3-319-09698-8_4

DO - 10.1007/978-3-319-09698-8_4

M3 - Conference contribution

AN - SCOPUS:84958538333

SN - 9783319096971

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

SP - 37

EP - 48

BT - Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings

PB - Springer Verlag

T2 - 18th International Conference on Developments in Language Theory, DLT 2014

Y2 - 26 August 2014 through 29 August 2014

ER -

State complexity of deletion

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this