Další formáty:
BibTeX
LaTeX
RIS
@article{198692,
author = {Černá, Ivana and Křetínský, Mojmír and Kučera, Antonín},
article_location = {Berlin},
article_number = {3},
keywords = {concurrency; bisimilarity; infinite-state systems},
language = {eng},
issn = {0001-5903},
journal = {Acta informatica},
title = {Comparing Expressibility of Normed BPA and Normed BPP Processes.},
volume = {36},
year = {1999}
}
TY - JOUR
ID - 198692
AU - Černá, Ivana - Křetínský, Mojmír - Kučera, Antonín
PY - 1999
TI - Comparing Expressibility of Normed BPA and Normed BPP Processes.
JF - Acta informatica
VL - 36
IS - 3
SP - 233
EP - 233
PB - Springer-Verlag
SN - 00015903
KW - concurrency
KW - bisimilarity
KW - infinite-state systems
N2 - We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \BPA\ and normed \BPP\ processes. We provide such a characterization for classes of normed BPA and normed BPP processes as well. Next we demonstrate decidability of the problem whether for a given normed \BPA\ process $\Delta$ there is some unspecified normed \BPP\ 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 the process $\Delta'$ is effectively constructible. Analogous algorithms are provided for normed \BPP\ processes. Simplified versions of the mentioned algorithms which work for nBPA and nBPP are given too. As a simple consequence we obtain decidability of bisimilarity in the union of normed \BPA\ and normed \BPP\ processes.
ER -
ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Comparing Expressibility of Normed BPA and Normed BPP Processes. \textit{Acta informatica}. Berlin: Springer-Verlag, roč.~36, č.~3, s.~233-256. ISSN~0001-5903. 1999.
|
