Informace o publikaci
Complexity in Union-Free Regular Languages
| Autoři | |
|---|---|
| Rok publikování | 2011 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | International Journal of Foundations of Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1142/S0129054111008933 |
| Doi | http://dx.doi.org/10.1142/S0129054111008933 |
| Obor | Informatika |
| Klíčová slova | Union-free regular language; finite automaton; one-cycle-free-path automaton; descriptional complexity; closure properties |
| Popis | 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. |