State complexity of projected languages
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F11%3A00362730" target="_blank" >RIV/67985840:_____/11:00362730 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-22600-7_16" target="_blank" >http://dx.doi.org/10.1007/978-3-642-22600-7_16</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-22600-7_16" target="_blank" >10.1007/978-3-642-22600-7_16</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
State complexity of projected languages
Popis výsledku v původním jazyce
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 transitionlabeled 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.
Název v anglickém jazyce
State complexity of projected languages
Popis výsledku anglicky
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 transitionlabeled 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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralizované a koordinační supervizní řízení</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Descriptional complexity of formal systems
ISBN
978-3-642-22599-4
ISSN
—
e-ISSN
—
Počet stran výsledku
14
Strana od-do
198-211
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Giessen/Limburg
Datum konání akce
25. 7. 2011
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—