Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Inproceedings3172
Abstract An automaton is partially ordered if the o
An automaton is partially ordered if the only cycles in its transition diagram are self-loops. We study the universality problem for ptNFAs, a class of partially ordered NFAs recognizing piecewise testable languages. The universality problem asks if an automaton accepts all words over its alphabet. Deciding universality for both NFAs and partially ordered NFAs is PSpace-complete. For ptNFAs, the complexity drops to coNP-complete if the alphabet is fixed but is open if the alphabet may grow. We show, using a novel and nontrivial construction, that the problem is PSpace-complete if the alphabet may grow polynomially.
ete if the alphabet may grow polynomially.  +
Author Tomáš Masopust + , Markus Krötzsch +
BibTex
@inproceedings{MK2018,
  author    = {Tom{\'{a}}{\v{s}} Masopust and Markus Kr{\"{o}}tzsch},
  title     = {Deciding Universality of {ptNFAs} is {PSpace-Complete}},
  editor    = {A Min Tjoa and Ladjel Bellatreche and Stefan Biffl and Jan van
               Leeuwen and Jiri Wiedermann},
  booktitle = {Proceedings of the 44th International Conference on Current
               Trends in Theory and Practice of Computer Science (SOFSEM 2018)},
  series    = {LNCS},
  volume    = {10706},
  publisher = {Springer},
  year      = {2018},
  pages     = {413-427},
  doi       = {10.1007/978-3-319-73117-9_29}
}
Bibtype Inproceedings  +
Booktitle Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018)  +
DOI Name 10.1007/978-3-319-73117-9_29  +
Download Masopust-Kroetzsch-ptNFA-Universality-Sofsem2018.pdf  +
Editor A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiri Wiedermann  +
ErsterAutorNachname Masopust  +
ErsterAutorVorname Tomáš  +
Forschungsgruppe Wissensbasierte Systeme +
ISBN 978-3-319-73116-2  +
Pages 413-427  +
Projekt Cfaed, DIAMOND, HAEC B08 + , Cfaed + , DIAMOND + , HAEC B08 +
Publication text Tomáš Masopust, Markus Krötzsch<br/>
Tomáš Masopust, Markus Krötzsch<br/> '''[[Inproceedings3172|<b>Deciding Universality of ptNFAs is PSpace-Complete</b>]]''' <br/>__NOTOC__In A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiri Wiedermann, eds., <i>Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018)</i>, volume 10706 of LNCS, 413-427, 2018. Springer<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3172|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:Masopust-Kroetzsch-ptNFA-Universality-Sofsem2018.pdf|Download]]
NFA-Universality-Sofsem2018.pdf|Download]]  +
Publication text en Tomáš Masopust, Markus Krötzsch<br/>
Tomáš Masopust, Markus Krötzsch<br/> '''[[Inproceedings3172/en|<b>Deciding Universality of ptNFAs is PSpace-Complete</b>]]''' <br/>__NOTOC__In A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiri Wiedermann, eds., <i>Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018)</i>, volume 10706 of LNCS, 413-427, 2018. Springer<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3172|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:Masopust-Kroetzsch-ptNFA-Universality-Sofsem2018.pdf|Download]]
NFA-Universality-Sofsem2018.pdf|Download]]  +
Publisher Springer  +
Referiert 1  +
Series LNCS  +
Title Deciding Universality of ptNFAs is PSpace-Complete  +
To appear 0  +
Type inproceedings  +
Volume 10706  +
Year 2018  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
Inproceedings3172 + , Inproceedings3172 + , Inproceedings3172 + , Inproceedings3172 + , Inproceedings3172 + , Inproceedings3172 +
Kategorien Inproceedings , Publikation
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
15 Januar 2019 19:39:16  +
verstecke Attribute die hierhin verlinken 
Inproceedings3172/en + Weiterleitungsseite
 

 

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