Article4031

PublikationenPublications

• Nach AutorBy Author
  • Tomáš MasopustTomáš Masopust
• Nach ForschungsgruppeBy Research Group
  • Wissensbasierte SystemeKnowledge-Based Systems

Toggle side column

Complexity in Union-Free Regular Languages

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

• Download
• DOI Link

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}
}