文章基本信息

标题：Branching Bisimilarity of Normed BPA Processes as a Rational Monoid
本地全文：下载
作者：Jancar, Petr
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2017
卷号：13
期号：4
语种：English
出版社：Technical University of Braunschweig
摘要：The paper presents an elaborated and simplified version of the structuralresult 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 computationalcomplexity, and a NEXPTIME-upper bound has been derived; the authors built onthe ideas by Fu (ICALP 2013), and strengthened his decidability result. LaterHe and Huang announced the EXPTIME-completeness of this problem (arxiv 1/2015,and LiCS 2015), giving a technical proof for the EXPTIME membership. He andHuang indirectly acknowledge the decomposition ideas by Czerwinski and Jancaron which they also built, but it is difficult to separate their starting pointfrom their new ideas. One aim here is to present the previous decompositionresult of Czerwinski and Jancar in a technically new framework, noting thatbranching bisimulation equivalence on normed BPA processes corresponds to arational monoid (in the sense of [Sakarovitch, 1987]); in particular it isshown that the mentioned equivalence can be decided by normal-form computingdeterministic finite transducers. Another aim is to provide a completedescription, including an informal overview, that should also make clear howFu's ideas were used, and to give all proofs in a form that should be readableand easily verifiable.
关键词：Computer Science - Formal Languages and Automata Theory;Computer Science - Logic in Computer Science