Jancar, Petr - Branching Bisimilarity of Normed BPA Processes as a Rational Monoid

lmcs:4097 - Logical Methods in Computer Science, November 28, 2017, Volume 13, Issue 4
Branching Bisimilarity of Normed BPA Processes as a Rational Monoid

Authors: Jancar, Petr

The paper presents an elaborated and simplified version of the structural result for branching bisimilarity on normed BPA (Basic Process Algebra) processes that was the crux of a conference paper by Czerwinski and Jancar (arxiv 7/2014 and LiCS 2015). That paper focused on the computational complexity, and a NEXPTIME-upper bound has been derived; the authors built on the ideas by Fu (ICALP 2013), and strengthened his decidability result. Later He and Huang announced the EXPTIME-completeness of this problem (arxiv 1/2015, and LiCS 2015), giving a technical proof for the EXPTIME membership. He and Huang indirectly acknowledge the decomposition ideas by Czerwinski and Jancar on which they also built, but it is difficult to separate their starting point from their new ideas. One aim here is to present the previous decomposition result of Czerwinski and Jancar in a technically new framework, noting that branching bisimulation equivalence on normed BPA processes corresponds to a rational monoid (in the sense of [Sakarovitch, 1987]); in particular it is shown that the mentioned equivalence can be decided by normal-form computing deterministic finite transducers. Another aim is to provide a complete description, including an informal overview, that should also make clear how Fu's ideas were used, and to give all proofs in a form that should be readable and easily verifiable.

Source : oai:arXiv.org:1602.05151
DOI : 10.23638/LMCS-13(4:17)2017
Volume: Volume 13, Issue 4
Published on: November 28, 2017
Submitted on: November 28, 2017
Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory


Consultation statistics

This page has been seen 141 times.
This article's PDF has been downloaded 76 times.