Počet záznamů: 1

State complexity of projected languages

  1. 1.
    0362730 - MU-W 2012 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
    Jirásková, G. - Masopust, Tomáš
    State complexity of projected languages.
    Descriptional Complexity of Formal Systems. Berlin: Springer, 2011 - (Holzer, M.; Kutrib, M.; Pighizzini, G.), s. 198-211. Lecture Notes in Computer Science, 6808. ISBN 978-3-642-22599-4.
    [13th International workshop, DCFS 2011. Giessen/Limburg (DE), 25.07.2011-27.07.2011]
    Grant CEP: GA ČR GPP202/11/P028
    Grant ostatní: European Commission(XE) EU.ICT.DISC 224498
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: descriptional complexity * state complexity * projection
    Kód oboru RIV: BA - Obecná matematika
    http://www.springerlink.com/content/h221760735tt7676/

    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.
    Trvalý link: http://hdl.handle.net/11104/0198970
    Název souboruStaženoVelikostKomentářVerzePřístup
    Masopust1.pdf1284.7 KBVydavatelský postprintvyžádat