State complexity of deletion and bipolar deletion
Loading...
Authors
Han, Yo-Sub
Ko, Sang-Ki
Salomaa, Kai
Date
2016
Type
journal article
Language
en
Keyword
formal languages, descriptional complexity
Alternative Title
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 \cdot 2^{n-1}$ (respectively, $(n + \frac{1}{2}) \cdot 2^n - 2$)
when using complete (respectively, incomplete) deterministic
finite automata.
We show that the state complexity of bipolar deletion
has an upper bound $n^n$ (respectively $(n+1)^n - 1$)
when using complete (respectively, incomplete)
deterministic finite automata. In both cases we give
almost matching lower bounds.
Description
Citation
DOI 10.1007/s00236-015-0245-y
Publisher
Springer-Verlag