On the State Complexity of the Reverse of R- and J-Trivial Regular Languages

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

ISBN: 978-3-642-39309-9
Download
DOI Link

Galina Jirásková, Tomáš Masopust
On the State Complexity of the Reverse of R- and J-Trivial Regular Languages
In H. Jurgensen and R. Reis, eds., Proc. of 15th International Workshop on Descriptional Complexity of Formal Systems (DCFS), volume 8031 of LNCS, 136-147, 2013. Springer

Details
Bibtex

KurzfassungAbstract
The tight bound on the state complexity of the reverse of R-trivial and J-trivial regular languages of the state complexity n is 2 n − 1. The witness is ternary for R-trivial regular languages and (n − 1)-ary for J-trivial regular languages. In this paper, we prove that the bound can be met neither by a binary R-trivial regular language nor by a J-trivial regular language over an (n − 2)-element alphabet. We provide a characterization of tight bounds for R-trivial regular languages depending on the state complexity of the language and the size of its alphabet. We show the tight bound for J-trivial regular languages over an (n − 2)-element alphabet and a few tight bounds for binary J-trivial regular languages. The case of J-trivial regular languages over an (n − k)-element alphabet, for 2 ≤ k ≤ n − 3, is open.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-39310-5_14.

@inproceedings{JM2013,
  author    = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
  title     = {On the State Complexity of the Reverse of R- and J-Trivial
               Regular Languages},
  editor    = {H. Jurgensen and R. Reis},
  booktitle = {Proc. of 15th International Workshop on Descriptional Complexity
               of Formal Systems (DCFS)},
  series    = {LNCS},
  volume    = {8031},
  publisher = {Springer},
  year      = {2013},
  pages     = {136-147},
  doi       = {10.1007/978-3-642-39310-5_14}
}