KUČERA, Antonín. The Complexity of Bisimilarity-Checking for One-Counter Processes. Theoretical Computer Science, Amsterdam, Nizozemí: Elsevier, 2003, vol. 304, 1-3, p. 157-183. ISSN 0304-3975.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
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 bisimilarity, concurrency, one-counter automata
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Changed: 22/11/2006 18:15.
Abstract
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 projectName: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Standard Projects
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, Research Intents
PrintDisplayed: 18/9/2020 14:44