On Büchi one-counter automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F17%3A10237379" target="_blank" >RIV/61989100:27240/17:10237379 - isvavai.cz</a>

Result on the web

<a href="http://drops.dagstuhl.de/opus/volltexte/2017/7019/" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2017/7019/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.14" target="_blank" >10.4230/LIPIcs.STACS.2017.14</a>

Result language

angličtina

Original language name

On Büchi one-counter automata

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA15-13784S" target="_blank" >GA15-13784S: Computational complexity of selected verification problems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2017

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs. Volume 66

ISBN

978-3-95977-028-6

ISSN

1868-8969

e-ISSN

neuvedeno

Number of pages

13

Pages from-to

1-13

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Place of publication

Wadern

Event location

Hannover

Event date

Mar 8, 2017

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—