KUČERA, Antonín. The Complexity of Bisimilarity-Checking for One-Counter Processes. Theoretical Computer Science. Amsterdam, Nizozemí: Elsevier, roč. 304, 1-3, s. 157-183. ISSN 0304-3975. 2003.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název The Complexity of Bisimilarity-Checking for One-Counter Processes
Autoři KUČERA, Antonín (203 Česká republika, garant).
Vydání Theoretical Computer Science, Amsterdam, Nizozemí, Elsevier, 2003, 0304-3975.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Nizozemské království
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.764
Kód RIV RIV/00216224:14330/03:00008108
Organizační jednotka Fakulta informatiky
UT WoS 000184305300007
Klíčová slova anglicky concurrency; one-counter automata; bisimilarity
Štítky bisimilarity, concurrency, one-counter automata
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 22. 11. 2006 18:15.
Anotace
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.
Návaznosti
GA201/03/1161, projekt VaVNázev: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů
VytisknoutZobrazeno: 28. 3. 2024 23:08