Complexity in Union-Free Regular Languages

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

ISBN: 978-3-642-14454-7
Download
DOI Link

Galina Jirásková, Tomáš Masopust
Complexity in Union-Free Regular Languages
In Y. Gao, H. Lu, S. Seki, S. Yu, eds., Proc. of 14th International Conference on Developments in Language Theory, volume 6224 of LNCS, 255-266, 2010. Springer

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

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-14455-4_24.

@inproceedings{JM2010,
  author    = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
  title     = {Complexity in Union-Free Regular Languages},
  editor    = {Y. Gao and H. Lu and S. Seki and S. Yu},
  booktitle = {Proc. of 14th International Conference on Developments in
               Language Theory},
  series    = {LNCS},
  volume    = {6224},
  publisher = {Springer},
  year      = {2010},
  pages     = {255-266},
  doi       = {10.1007/978-3-642-14455-4_24}
}