Paper Info
Title
An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free Processes
Abstract
Abstract: We present an elementary algorithm for deciding bisimulation equivalence betweenarbitrary context-free processes. This improves on the state of the art algorithmof Christensen, Huttel and Stirling consisting of two semi-decision proceduresrunning in parallel, which prohibits any complexity estimation. The point of ouralgorithm is the effective construction of a finite relation characterizing all bisimulationequivalence classes, whose mere existence was exploited for the above...
Year
DOI
Venue
1995
10.1007/3-540-60246-1_148
MFCS
Keywords
Field
DocType
arbitrary context-free processes,elementary bisimulation decision procedure
Discrete mathematics,Combinatorics,Binary relation,Decidability,Bisimulation,Bisimulation equivalence,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-60246-1
42
1.83
References 
Authors
14
3
Name
Order
Citations
PageRank
Olaf Burkart128736.17
Didier Caucal247039.15
Bernhard Steffen34239423.70