TY - GEN
T1 - A quasi-local algorithm for checking bisimilarity
AU - Du, Wenjie
AU - Deng, Yuxin
PY - 2011
Y1 - 2011
N2 - Bisimilarity is one of the most important relations for comparing the behaviour of formal systems in concurrency theory. Decision algorithms for bisimilarity in finite state systems are usually classified into two kinds: global algorithms are generally efficient but require to generate the whole state spaces in advance, local algorithms combine the verification of a system's behaviour with the generation of the system's state space, which is often more effective to determine that one system fails to be related to another. In this paper we propose a quasi-local algorithm with worst case time complexity O(m1m2), where m1 and m2 are the numbers of transitions in two labelled transition systems. With mild modifications, the algorithm can be easily adapted to decide similarity with the same time complexity. For deterministic systems, the algorithm can be simplified and runs in time O(min(m1,m2)).
AB - Bisimilarity is one of the most important relations for comparing the behaviour of formal systems in concurrency theory. Decision algorithms for bisimilarity in finite state systems are usually classified into two kinds: global algorithms are generally efficient but require to generate the whole state spaces in advance, local algorithms combine the verification of a system's behaviour with the generation of the system's state space, which is often more effective to determine that one system fails to be related to another. In this paper we propose a quasi-local algorithm with worst case time complexity O(m1m2), where m1 and m2 are the numbers of transitions in two labelled transition systems. With mild modifications, the algorithm can be easily adapted to decide similarity with the same time complexity. For deterministic systems, the algorithm can be simplified and runs in time O(min(m1,m2)).
KW - Concurrency
KW - algorithm
KW - bisimilarity
KW - labelled transition systems
UR - https://www.scopus.com/pages/publications/80051865397
U2 - 10.1109/CSAE.2011.5952411
DO - 10.1109/CSAE.2011.5952411
M3 - 会议稿件
AN - SCOPUS:80051865397
SN - 9781424487257
T3 - Proceedings - 2011 IEEE International Conference on Computer Science and Automation Engineering, CSAE 2011
SP - 1
EP - 5
BT - Proceedings - 2011 IEEE International Conference on Computer Science and Automation Engineering, CSAE 2011
T2 - 2011 IEEE International Conference on Computer Science and Automation Engineering, CSAE 2011
Y2 - 10 June 2011 through 12 June 2011
ER -