Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Henning Fernau, Petra Wolf, and Tomoyuki Yamakami. Synchronizing Deterministic Push-Down Automata Can Be Really Hard. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fernau_et_al:LIPIcs.MFCS.2020.33, author = {Fernau, Henning and Wolf, Petra and Yamakami, Tomoyuki}, title = {{Synchronizing Deterministic Push-Down Automata Can Be Really Hard}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {33:1--33:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.33}, URN = {urn:nbn:de:0030-drops-127008}, doi = {10.4230/LIPIcs.MFCS.2020.33}, annote = {Keywords: Synchronizing automaton, Reset sequence, Real-time deterministic push-down automaton, Finite-turn push-down automaton, Computability, Computational complexity} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Tomoyuki Yamakami. The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{yamakami:LIPIcs.MFCS.2017.62, author = {Yamakami, Tomoyuki}, title = {{The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {62:1--62:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.62}, URN = {urn:nbn:de:0030-drops-81344}, doi = {10.4230/LIPIcs.MFCS.2017.62}, annote = {Keywords: sub-linear space, linear space hypothesis, short reduction, Boolean formula satisfiability problem, NL search, NL optimization, Syntactic NL} }
Feedback for Dagstuhl Publishing