On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs

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

ISBN: 978-3-642-31605-0
Download
DOI Link

Galina Jirásková, Tomáš Masopust
On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
In N. Moreira, R. Reis, eds., Proc. of 17th International Conference on Implementation and Application of Automata (CIAA), volume 7381 of LNCS, 229-239, 2012. Springer

Details
Bibtex

KurzfassungAbstract
We study the state complexity of the reverse of acyclic minimal deterministic finite automata, and the computational complexity of the following problem: Given an acyclic minimal DFA, is the minimal DFA for the reverse also acyclic? Note that we allow self-loops in acyclic automata. We show that there exists a language accepted by an acyclic minimal DFA such that the minimal DFA for its reverse is exponential with respect to the number of states, and we establish a tight bound on the state complexity of the reverse of acyclic DFAs. We also give a direct proof of the fact that the minimal DFA for the reverse is acyclic if and only if the original acyclic minimal DFA satisfies a certain structural property, which can be tested in quadratic time.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-31606-7_20.

@inproceedings{JM2012,
  author    = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
  title     = {On the State and Computational Complexity of the Reverse of
               Acyclic Minimal {DFAs}},
  editor    = {N. Moreira and R. Reis},
  booktitle = {Proc. of 17th International Conference on Implementation and
               Application of Automata (CIAA)},
  series    = {LNCS},
  volume    = {7381},
  publisher = {Springer},
  year      = {2012},
  pages     = {229-239},
  doi       = {10.1007/978-3-642-31606-7_20}
}