Other formats:
BibTeX
LaTeX
RIS
@article{487652,
author = {Kučera, Antonín},
article_location = {Amsterdam, Nizozemí},
article_number = {1-3},
keywords = {concurrency; one-counter automata; bisimilarity},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {The Complexity of Bisimilarity-Checking for One-Counter Processes},
volume = {304},
year = {2003}
}
TY - JOUR
ID - 487652
AU - Kučera, Antonín
PY - 2003
TI - The Complexity of Bisimilarity-Checking for One-Counter Processes
JF - Theoretical Computer Science
VL - 304
IS - 1-3
SP - 157-183
EP - 157-183
PB - Elsevier
SN - 03043975
KW - concurrency
KW - one-counter automata
KW - bisimilarity
N2 - We study the problem of bisimilarity-checking between processes of one-counter automata and finite-state processes. We show that deciding weak bisimilarity between processes of one-counter nets and finite-state processes is DP-hard. Then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and finite-state processes in time which is polynomial for a large subclass of instances, giving a kind of characterization of all hard instances as a byproduct.
ER -
KUČERA, Antonín. The Complexity of Bisimilarity-Checking for One-Counter Processes. \textit{Theoretical Computer Science}. Amsterdam, Nizozemí: Elsevier, 2003, vol.~304, 1-3, p.~157-183. ISSN~0304-3975.
|
