Partially-commutative context-free processes: Expressibility and tractability |
| |
Authors: | Wojciech Czerwiński Sibylle FröschleS?awomir Lasota |
| |
Affiliation: | a Institute of Informatics, University of Warsaw, Warsaw, Poland b Universität Oldenburg, Fakultät II, Department für Informatik, 26111 Oldenburg, Germany |
| |
Abstract: | Bisimulation equivalence is decidable in polynomial time for both sequential and commutative normed context-free processes, known as BPA and BPP, respectively. Despite apparent similarity between the two classes, different algorithmic techniques were used in each case. We provide one polynomial-time algorithm that works in a superclass of both normed BPA and BPP. It is derived in the setting of partially-commutative context-free processes, a new process class introduced in the paper. It subsumes both BPA and BPP and seems to be of independent interest. Expressibility issue of the new class, in comparison with the normed PA class, is also tackled in the paper. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|