Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F16%3A86100159" target="_blank" >RIV/61989100:27240/16:86100159 - isvavai.cz</a>
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2016/6464/" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2016/6464/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.52" target="_blank" >10.4230/LIPIcs.MFCS.2016.52</a>
Alternative languages
Result language
angličtina
Original language name
Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
Original language description
The problem if a given configuration of a pushdown automaton (PDA) is bisimilar with some (unspecified) finite-state process is shown to be decidable. The decidability is proven in the framework of first-order grammars, which are given by finite sets of labelled rules that rewrite roots of first-order terms. The framework is equivalent to PDA where also deterministic popping epsilon-steps are allowed, i.e. To the model for which Sénizergues showed an involved procedure deciding bisimilarity (FOCS 1998). Such a procedure is here used as a black-box part of the algorithm. For deterministic PDA the regularity problem was shown decidable by Valiant (JACM 1975) but the decidability question for nondeterministic PDA, answered positively here, had been open (as indicated, e.g., by Broadbent and Goeller, FSTTCS 2012).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
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)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs. Volume 58
ISBN
978-3-95977-016-3
ISSN
1868-8969
e-ISSN
—
Number of pages
13
Pages from-to
"52:1-"-"-52:13"
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Place of publication
Wadern
Event location
Krakov
Event date
Aug 22, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—