Comparing expressibility of normed BPA and normed BPP processes
type: Item
instance of: scholarly article
title: Comparing expressibility of normed BPA and normed BPP processes
zbMATH Open document ID: 0947.68109
author: I. Černá
author: Mojmír Křetínský
author: Antonin Kučera
published in: Acta Informatica
publication date: 1999-11-29T00:00:00Z
review text: We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \(\text{BPA}_\tau\) and normed \(\text{BPP}_\tau\) processes. We give such a characterization for the subclasses of normed BPA and normed BPP processes as well. Next, we demonstrate the decidability of the problem whether for a given normed \(\text{BPA}_\tau\) process \(\Delta\) there is some unspecified normed \(\text{BPP}_\tau\) process \(\Delta'\) such that \(\Delta\) and \(\Delta'\) are bisimilar. The algorithm is polynomial. Furthermore, we show that if the answer to the previous question is positive, then (an example of) the process \(\Delta'\) is effectively constructible. Analogous algorithms are provided for normed \(\text{BPP}_\tau\) processes. Simplified versions of the mentioned algorithms which work for normed BPA and normed BPP are given, too. As a simple consequence we obtain the decidability of bisimilarity in the union of normed \(\text{BPA}_\tau\) and normed \(\text{BPP}_\tau\) processes.
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 1347426
zbMATH Keywords: transition systems
MaRDI profile type: Publication
full work available at URL: s002360050159
OpenAlex ID: W2059660155
DOI: 10.1007/S002360050159
description: scientific article; zbMATH DE number 1347426