The Complexity of Bisimilarity-Checking for One-Counter Processes

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KUČERA Antonín

Year of publication 2003
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords concurrency; one-counter automata; bisimilarity
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info