Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F04%3A00010251" target="_blank" >RIV/00216224:14330/04:00010251 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems
Original language description
We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. For normed subclasses of probabilistic BPA and BPP processes we obtain polynomial-time algorithms. Further, we show that probabilistic bisimilarity between probabilistic pushdown automata and finite-state systems is decidable in exponential time. If the number of control states in PDA is bounded by a fixed constant, then the algorithm needs only polynomial time.
Czech name
Rozhodnutelnost pravděpodobnostní bisimulace pro nekonečně-stavové pravděpodobnostní systémy
Czech description
V článku je dokázáno, že pravděpodobnostní bisimulace je rozhodnutelná pro pravděpodobnostní rozšíření BPA a BPP procesů. Pro normované podtřídy pravděpodobnostních BPA a BPP procesů jsou prezentovány algoritmy, jejichž časová složitost je polynomiální.Dále je dokázáno, že pravděpodobnostní bisimulace mezi pravděpodobnostními zásobníkovými automaty a konečně-stavovými pravděpodobnostními systémy je rozhodnutelná v exponenciálním čase. Pokud je počet kontrolních stavů zásobníkového automatu omezen fixníkonstantou, pak je tato časová složitost polynomiální.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F03%2F1161" target="_blank" >GA201/03/1161: Verification of infinite-state systems</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004)
ISBN
3-540-22940-X
ISSN
—
e-ISSN
—
Number of pages
16
Pages from-to
193-208
Publisher name
Springer
Place of publication
Berlin
Event location
August 31 - September 3, 2004, London, UK
Event date
Jan 1, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—