Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Inproceedings3007
Abstract We study the state complexity of the rever
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.
ty, which can be tested in quadratic time.  +
Author Galina Jirásková + , Tomáš Masopust +
BibTex
@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}
}
Bibtype Inproceedings  +
Booktitle Proc. of 17th International Conference on Implementation and Application of Automata (CIAA)  +
DOI Name 10.1007/978-3-642-31606-7_20  +
Download On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs.pdf  +
Editor N. Moreira, R. Reis  +
ErsterAutorNachname Jirásková  +
ErsterAutorVorname Galina  +
Forschungsgruppe Wissensbasierte Systeme +
ISBN 978-3-642-31605-0  +
Pages 229-239  +
Publication text Galina Jirásková, Tomáš Masopust<br/>
Galina Jirásková, Tomáš Masopust<br/> '''[[Inproceedings3007|<b>On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs</b>]]''' <br/>__NOTOC__In N. Moreira, R. Reis, eds., <i>Proc. of 17th International Conference on Implementation and Application of Automata (CIAA)</i>, volume 7381 of LNCS, 229-239, 2012. Springer<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3007|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs.pdf|Download]]
rse of Acyclic Minimal DFAs.pdf|Download]]  +
Publication text en Galina Jirásková, Tomáš Masopust<br/>
Galina Jirásková, Tomáš Masopust<br/> '''[[Inproceedings3007/en|<b>On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs</b>]]''' <br/>__NOTOC__In N. Moreira, R. Reis, eds., <i>Proc. of 17th International Conference on Implementation and Application of Automata (CIAA)</i>, volume 7381 of LNCS, 229-239, 2012. Springer<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3007|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs.pdf|Download]]
rse of Acyclic Minimal DFAs.pdf|Download]]  +
Publisher Springer  +
Referiert 1  +
Series LNCS  +
Title On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs  +
To appear 0  +
Type inproceedings  +
Volume 7381  +
Year 2012  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
Inproceedings3007 + , Inproceedings3007 + , Inproceedings3007 + , Inproceedings3007 + , Inproceedings3007 + , Inproceedings3007 +
Kategorien Publikation , Inproceedings
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
24 Mai 2016 16:02:19  +
verstecke Attribute die hierhin verlinken 
Inproceedings3007/en + Weiterleitungsseite
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.