State complexity of deletion and bipolar deletion

Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/s00236-015-0245-y

State complexity of deletion and bipolar deletion

Yo Sub Han, Sang Ki Ko, Kai Salomaa

Department of Artificial Intelligence

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

7 Scopus citations

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 (Formula presented.) [respectively, (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. We show that the state complexity of bipolar deletion has an upper bound (Formula presented.) [respectively (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. In both cases we give almost matching lower bounds.

Original language	English
Pages (from-to)	67-85
Number of pages	19
Journal	Acta Informatica
Volume	53
Issue number	1
DOIs	https://doi.org/10.1007/s00236-015-0245-y
State	Published - 1 Feb 2016

Access to Document

10.1007/s00236-015-0245-y

Cite this

@article{3f8e12bbbde449359065da6cbe5b9eb1,

title = "State complexity of deletion and bipolar 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 (Formula presented.) [respectively, (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. We show that the state complexity of bipolar deletion has an upper bound (Formula presented.) [respectively (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. In both cases we give almost matching lower bounds.",

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

note = "Publisher Copyright: {\textcopyright} 2015, Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = feb,

day = "1",

doi = "10.1007/s00236-015-0245-y",

language = "English",

volume = "53",

pages = "67--85",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - State complexity of deletion and bipolar deletion

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2016/2/1

Y1 - 2016/2/1

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 (Formula presented.) [respectively, (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. We show that the state complexity of bipolar deletion has an upper bound (Formula presented.) [respectively (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. In both cases we give almost matching lower bounds.

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 (Formula presented.) [respectively, (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. We show that the state complexity of bipolar deletion has an upper bound (Formula presented.) [respectively (Formula presented.) ] when using complete (respectively, incomplete) deterministic finite automata. In both cases we give almost matching lower bounds.

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

U2 - 10.1007/s00236-015-0245-y

DO - 10.1007/s00236-015-0245-y

M3 - Article

AN - SCOPUS:84958167092

SN - 0001-5903

VL - 53

SP - 67

EP - 85

JO - Acta Informatica

JF - Acta Informatica

IS - 1

ER -

State complexity of deletion and bipolar deletion

Abstract

Access to Document

Other files and links

Fingerprint

Cite this