Publication details
Complexity in Union-Free Regular Languages
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Proceedings |
| Conference | DLT 2010, LNCS 6224 |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1007/978-3-642-14455-4_24 |
| Field | Informatics |
| Keywords | Descriptional complexity, union-free regular language, one-cycle-free-path finite automaton. |
| Description | 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. |