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.MFCS.2016.52
URN: urn:nbn:de:0030-drops-64649
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6464/
Go to the corresponding LIPIcs Volume Portal

Jancar, Petr

Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence

pdf-format:
LIPIcs-MFCS-2016-52.pdf (0.4 MB)

Abstract

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 Senizergues 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).

BibTeX - Entry

@InProceedings{jancar:LIPIcs:2016:6464,
  author =	{Petr Jancar},
  title =	{{Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{52:1--52:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6464},
  URN =		{urn:nbn:de:0030-drops-64649},
  doi =		{10.4230/LIPIcs.MFCS.2016.52},
  annote =	{Keywords: pushdown processes, first-order grammars, bisimulation, regularity}
}

Keywords: pushdown processes, first-order grammars, bisimulation, regularity
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

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