Paper Info
Title
Expansive-bisimulation for context-free processes
Abstract
Through the notion of expansive-bisimulation, in this paper we give a finite characterization of bisimulation equivalence for contextfree processes, i.e. we show that two context-free processes are bisimulation equivalent if and only if there is a finite expansive-bisimulation which contains them. This immediately suggests the set of finite expansivebisimulation as a complete class of verifiable evidence for bisimulation equality of context-free processes. Compared with the well known result that two context-free processes are bisimulation equivalent if and only if there is a finite self-bisimulation which relates them, the new result made improvement in the sense that whether a finite relation is an expansive-bisimulation is decidable while whether a finite relation is a self-bisimulation is only semi-decidable.
Year
DOI
Venue
2007
null
Formal Methods and Hybrid Real-Time Systems
Field
DocType
Volume
Algebra,Computer science,Binary relation,Algorithm,Decidability,Theoretical computer science,Verifiable secret sharing,If and only if,Bisimulation,Expansive,Bisimulation equivalence
Conference
4700 LNCS
Issue
ISSN
ISBN
null
0302-9743
3-540-75220-X
Citations 
PageRank 
References 
0
0.34
10
Authors
1
Name
Order
Citations
PageRank
Xinxin Liu11518.79