Počet záznamů: 1

Complexity in Union-Free Regular Languages

  1. 1.
    0346729 - MU-W 2011 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
    Jirásková, G. - Masopust, Tomáš
    Complexity in Union-Free Regular Languages.
    Developments in Language Theory. Berlin: Springer, 2010 - (Gao, Y.; Lu, H.; Seki, S.), s. 255-266. Lecture Notes in Computer Science, 6224. ISBN 978-3-642-14455-4.
    [DLT2010. 14th International Conference on Developments in Language Theory. London (CA), 17.08.2010-20.08.2010]
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: descriptional complexity * union-free regular language * one-cycle-free-path finite automaton
    Kód oboru RIV: BA - Obecná matematika
    http://link.springer.com/chapter/10.1007%2F978-3-642-14455-4_24

    We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages recognized by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.
    Trvalý link: http://hdl.handle.net/11104/0187671
    Název souboruStaženoVelikostKomentářVerzePřístup
    Masopust2.pdf1242.6 KBVydavatelský postprintvyžádat