License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.14
URN: urn:nbn:de:0030-drops-70194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7019/
Go to the corresponding LIPIcs Volume Portal

Böhm, Stanislav ; Göller, Stefan ; Halfon, Simon ; Hofman, Piotr

On Büchi One-Counter Automata

pdf-format:
LIPIcs-STACS-2017-14.pdf (0.6 MB)

Abstract

Equivalence of deterministic pushdown automata is a famous problem in theoretical computer science whose decidability has been shown by Sénizergues. Our first result shows that decidability no longer holds when moving from finite words to infinite words. This solves an open problem that has recently been raised by Löding. In fact, we show that already the equivalence problem for deterministic Büchi one-counter automata is undecidable. Hence, the decidability border is rather tight when taking into account a recent result by Löding and Repke that equivalence of deterministic weak parity pushdown automata (a subclass of deterministic Büchi pushdown automata) is decidable.

Another known result on finite words is that the universality problem for vector addition systems is decidable. We show undecidability when moving to infinite words. In fact, we prove that already the universality problem for nondeterministic Büchi one-counter nets (or equivalently vector addition systems with one unbounded dimension) is undecidable.

BibTeX - Entry

@InProceedings{bhm_et_al:LIPIcs:2017:7019,
  author =	{Stanislav B{\"o}hm and Stefan G{\"o}ller and Simon Halfon and Piotr Hofman},
  title =	{{On B{\"u}chi One-Counter Automata}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7019},
  URN =		{urn:nbn:de:0030-drops-70194},
  doi =		{10.4230/LIPIcs.STACS.2017.14},
  annote =	{Keywords: infinite words, deterministic pushdown automata}
}

Keywords: infinite words, deterministic pushdown automata
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI