06073870

j

06073870 Jir\'askov\'a, Galina Masopust, Tom\'a\v{s} Complexity in union-free regular languages. Int. J. Found. Comput. Sci. 22, No. 7, 1639-1653 (2011). 2011 World Scientific, Singapore EN union-free regular language finite automaton one-cycle-free-path automaton descriptional complexity closure properties

doi:10.1142/S0129054111008933

Summary: 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.