International Journal of Foundations of Computer Science · 2011 · 41 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationAutomata TheoryComputational ComplexityFinite AutomataFinite-state MachinesFormal Language FoundationsRegular LanguagesComputational Complexity Of LanguagesDeterministic Finite AutomataFinite Automata TheoryNondeterministic Finite AutomataRegular ExpressionsRegular OperationsUnionUnion Operation
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.
18