Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{938256, author = {Jirásková, Galina and Masopust, Tomáš}, address = {Heidelberg}, booktitle = {DCFS 2011, LNCS 6808}, editor = {M. Holzer, M. Kutrib, and G. Pighizzini}, keywords = {Descriptional complexity, state complexity, projection.}, language = {eng}, location = {Heidelberg}, pages = {198-211}, publisher = {Springer}, title = {State Complexity of Projected Languages}, year = {2011} }
TY - JOUR ID - 938256 AU - Jirásková, Galina - Masopust, Tomáš PY - 2011 TI - State Complexity of Projected Languages PB - Springer CY - Heidelberg KW - Descriptional complexity, state complexity, projection. N2 - 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. ER -
JIRÁSKOVÁ, Galina a Tomáš MASOPUST. State Complexity of Projected Languages. In M. Holzer, M. Kutrib, and G. Pighizzini. \textit{DCFS 2011, LNCS 6808}. Heidelberg: Springer, 2011, s.~198-211. ISSN~0302-9743.
|