COMPLEXITY IN UNION-FREE REGULAR LANGUAGES

摘要

We continue the investigation of union-free regular languages that are described byregular expressions without the union operation. We also define deterministic union-freelanguages 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 provethat (deterministic) union-freeness of languages does not accelerate regular operations,except for the reversal in the nondeterministic case.