Počet záznamů: 1

State complexity of projected languages

SYSNO ASEP	0362730
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	State complexity of projected languages
Tvůrce(i)	Jirásková, G. (SK) Masopust, Tomáš (MU-W)_{RID, ORCID, SAI}
Zdroj.dok.	Descriptional Complexity of Formal Systems. - Berlin : Springer, 2011 / Holzer M. ; Kutrib M. ; Pighizzini G. - ISBN 978-3-642-22599-4
Rozsah stran	s. 198-211
Poč.str.	14 s.
Akce	13th International workshop, DCFS 2011
Datum konání	25.07.2011-27.07.2011
Místo konání	Giessen/Limburg
Země	DE - Německo
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	DE - Německo
Klíč. slova	descriptional complexity ; state complexity ; projection
Vědní obor RIV	BA - Obecná matematika
CEP	GPP202/11/P028 GA ČR - Grantová agentura ČR
CEZ	AV0Z10190503 - MU-W (2005-2011)
EID SCOPUS	79961197594
DOI	10.1007/978-3-642-22600-7_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.
Pracoviště	Matematický ústav
Kontakt	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Rok sběru	2012

Počet záznamů: 1