Number of the records: 1
State complexity of projected languages
- 1.
SYSNO ASEP 0362730 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title State complexity of projected languages Author(s) Jirásková, G. (SK)
Masopust, Tomáš (MU-W) RID, ORCID, SAISource Title Descriptional Complexity of Formal Systems. - Berlin : Springer, 2011 / Holzer M. ; Kutrib M. ; Pighizzini G. - ISBN 978-3-642-22599-4 Pages s. 198-211 Number of pages 14 s. Action 13th International workshop, DCFS 2011 Event date 25.07.2011-27.07.2011 VEvent location Giessen/Limburg Country DE - Germany Event type WRD Language eng - English Country DE - Germany Keywords descriptional complexity ; state complexity ; projection Subject RIV BA - General Mathematics R&D Projects GPP202/11/P028 GA ČR - Czech Science Foundation (CSF) CEZ AV0Z10190503 - MU-W (2005-2011) EID SCOPUS 79961197594 DOI 10.1007/978-3-642-22600-7_16 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2012
Number of the records: 1