On a structural property in the state complexity of projected regular languages

JIRÁSKOVÁ, Galina a Tomáš MASOPUST. On a structural property in the state complexity of projected regular languages. Theoretical Computer Science. Amsterdam, North Holland: Elsevier Science Publishers, 2012, roč. 449, s. 93-105. ISSN 0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2012.04.009.

Základní údaje

Originální název

On a structural property in the state complexity of projected regular languages

Autoři

JIRÁSKOVÁ, Galina a Tomáš MASOPUST

Vydání

Theoretical Computer Science, Amsterdam, North Holland, Elsevier Science Publishers, 2012, 0304-3975

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 0.489

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/j.tcs.2012.04.009

UT WoS

000306771300009

Klíčová slova česky

Projections; State complexity; Descriptional complexity

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

A transition is unobservable if it is labeled by a symbol removed by a projection. The present paper investigates a new structural property of incomplete deterministic finite automata - a number of states incident with an unobservable transition - and its effect on the state complexity of projected regular languages. We show that the known upper bound can be met only by automata with one unobservable transition (up to unobservable multi-transitions). We improve this upper bound by taking into consideration the structural property of minimal incomplete automata, and prove the tightness of new upper bounds. Special attention is focused on the case of finite languages. The paper also presents and discusses several fundamental problems which are still open.