Complexity in union-free regular languages

0369498 - MÚ 2012 RIV SG eng J - Journal Article
Jirásková, G. - Masopust, Tomáš
Complexity in union-free regular languages.
International Journal of Foundations of Computer Science. Roč. 22, č. 7 (2011), s. 1639-1653. ISSN 0129-0541. E-ISSN 1793-6373
Institutional research plan: CEZ:AV0Z10190503
Keywords : Union-free regular language * one-cycle-free-path automaton * descriptional complexity
Subject RIV: BA - General Mathematics
Impact factor: 0.379, year: 2011
http://www.worldscinet.com/ijfcs/22/2207/S0129054111008933.html

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 accepted 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.
Permanent Link: http://hdl.handle.net/11104/0203547