Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time | Zendy

Martin Kot | Zendy; Zdeněk Sawa | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time

Author(s) -

Martin Kot,

Zdeněk Sawa

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.02.065

Subject(s) - bisimulation , equivalence (formal languages) , mathematics , time complexity , state (computer science) , finite state machine , finite set , representation (politics) , discrete mathematics , algebra over a field , algorithm , pure mathematics , mathematical analysis , politics , political science , law

In this paper we consider the problem of deciding bisimulation equivalence of a BPP and a finite-state system. We show that the problem can be solved in polynomial time and we present an algorithm deciding the problem in time O(n4). The algorithm also constructs for each state of the finite-state system a ‘symbolic’ semilinear representation of the set of all states of the BPP system which are bisimilar with this state

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research