The complexity of bisimilarity-checking for one-counter processes

✍ Scribed by Antonı́n Kučera

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 376 KB
• Volume: 304
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00081-1

✦ Synopsis

We study the problem of bisimilarity-checking between processes of one-counter automata and ÿnite-state processes. We show that deciding weak bisimilarity between processes of one-counter nets (which are 'restricted' one-counter automata where the counter cannot be tested for zero) and ÿnite-state processes is DP-hard. In particular, this means that the problem is both NP and co-NP hard. The same technique is used to demonstrate co-NP-hardness of strong bisimilarity between processes of one-counter nets. Then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and ÿnite-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. Moreover, we show how to e ciently estimate the time which is needed to solve a given instance. Finally, we prove that the problem of strong bisimilarity between processes of one-counter automata and ÿnite-state processes is in P.