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.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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
Organizační jednotka Fakulta informatiky
ISSN 0302-9743
Klíčová slova anglicky Descriptional complexity, state complexity, projection.
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Změněno: 2. 6. 2011 17:16.
Anotace
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.
VytisknoutZobrazeno: 12. 6. 2024 08:08