Complexity in Union-Free Regular Languages

Galina JiráskováGalina Jirásková, Tomáš MasopustTomáš Masopust

Galina Jirásková, Tomáš Masopust
Complexity in Union-Free Regular Languages
International Journal of Foundations of Computer Science, 22(7):1639-1653, 2011

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@article{JM2011,
  author  = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
  title   = {Complexity in Union-Free Regular Languages},
  journal = {International Journal of Foundations of Computer Science},
  volume  = {22},
  number  = {7},
  year    = {2011},
  pages   = {1639-1653},
  doi     = {10.1142/S0129054111008933}
}