J 2003

The Complexity of Bisimilarity-Checking for One-Counter Processes

KUČERA, Antonín

Basic information

Original name

The Complexity of Bisimilarity-Checking for One-Counter Processes

Authors

KUČERA, Antonín (203 Czech Republic, guarantor)

Edition

Theoretical Computer Science, Amsterdam, Nizozemí, Elsevier, 2003, 0304-3975

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.764

RIV identification code

RIV/00216224:14330/03:00008108

Organization unit

Faculty of Informatics

UT WoS

000184305300007

Keywords in English

concurrency; one-counter automata; bisimilarity

Tags

Tags

International impact, Reviewed
Změněno: 22/11/2006 18:15, prof. RNDr. Antonín Kučera, Ph.D.

Abstract

V originále

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.

Links

GA201/03/1161, research and development project
Name: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Verification of infinite-state systems
MSM 143300001, plan (intention)
Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing