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.
|