Complexity in Union-Free Regular Languages

0346729 - MÚ 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