State Complexity of Projected Languages

JIRÁSKOVÁ, Galina a Tomáš MASOPUST. State Complexity of Projected Languages. In M. Holzer, M. Kutrib, and G. Pighizzini. DCFS 2011, LNCS 6808. Heidelberg: Springer, 2011, s. 198-211. ISSN 0302-9743.

Základní údaje

Originální název

State Complexity of Projected Languages

Autoři

JIRÁSKOVÁ, Galina a Tomáš MASOPUST

Vydání

Heidelberg, DCFS 2011, LNCS 6808, od s. 198-211, 2011

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISSN

Klíčová slova anglicky

Descriptional complexity, state complexity, projection.

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

This paper discusses the state complexity of projected regular languages represented by incomplete deterministic finite automata. It is shown that the known upper bound is reachable only by automata with one unobservable transition, that is, a transition labeled with a symbol removed by the projection. The present paper improves this upper bound by considering the structure of the automaton. It also proves that the new bounds are tight, considers the case of finite languages, and presents several open problems.