CCS expressions, finite state processes, and three problems of equivalence Export

@inproceedings{citeulike:3353441, abstract = {We examine the computational complexity of testing finite state processes for equivalence, in the Calculus of Communicating Systems (CCS). This equivalence problem in CCS is presented as a refinement of the familiar problem of testing whether two nondeterministic finite state automata (n.f.s.a.) accept the same language. Three notions of equivalence, proposed for CCS, are investigated: (1) observation equivalence, (2) congruence, and (3) failure equivalence. We show that observation equivalence (@@@@) can be tested in cubic time and is the limit of a sequence of equivalence notions (@@@@ k ), where, @@@@ 1 is the familiar n.f.s.a. equivalence and, for each fixed k , @@@@ k is PSPACE-complete. We provide an O ( nlogn ) test for congruence for n state processes of bounded fanout, by extending the algorithm that minimizes the states of d.f.s.a.'s. Finally, we show that, even for a very restricted type of process, testing for failure equivalence is PSPACE-complete.}, address = {New York, NY, USA}, author = {Kanellakis, Paris C. and Smolka, Scott A.}, booktitle = {PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing}, citeulike-article-id = {3353441}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=800221.806724}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/800221.806724}, comment = {contains an overview of the approach to finding role equivalence.}, doi = {10.1145/800221.806724}, isbn = {0-89791-110-5}, keywords = {analysis, equivalence, role, social-network-analysis, social-network-anaylsis, social-networking, social-networks, socialnetworks}, location = {Montreal, Quebec, Canada}, pages = {228--240}, posted-at = {2009-09-14 10:08:38}, priority = {2}, publisher = {ACM}, title = {CCS expressions, finite state processes, and three problems of equivalence}, url = {http://dx.doi.org/10.1145/800221.806724}, year = {1983} }

TY - CONF ID - citeulike:3353441 L3 - citeulike-article-id:3353441 N2 - We examine the computational complexity of testing finite state processes for equivalence, in the Calculus of Communicating Systems (CCS). This equivalence problem in CCS is presented as a refinement of the familiar problem of testing whether two nondeterministic finite state automata (n.f.s.a.) accept the same language. Three notions of equivalence, proposed for CCS, are investigated: (1) observation equivalence, (2) congruence, and (3) failure equivalence. We show that observation equivalence (@@@@) can be tested in cubic time and is the limit of a sequence of equivalence notions (@@@@ k ), where, @@@@ 1 is the familiar n.f.s.a. equivalence and, for each fixed k , @@@@ k is PSPACE-complete. We provide an O ( nlogn ) test for congruence for n state processes of bounded fanout, by extending the algorithm that minimizes the states of d.f.s.a.'s. Finally, we show that, even for a very restricted type of process, testing for failure equivalence is PSPACE-complete. CY - Montreal, Quebec, Canada SN - 0-89791-110-5 AD - New York, NY, USA EP - 240 TI - CCS expressions, finite state processes, and three problems of equivalence PB - ACM T2 - PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing SP - 228 KW - analysis KW - equivalence KW - role KW - social-network-analysis KW - social-network-anaylsis KW - social-networking KW - social-networks KW - socialnetworks N1 - contains an overview of the approach to finding role equivalence. AU - Kanellakis, Paris AU - Smolka, Scott PY - 1983/// UR - http://dx.doi.org/10.1145/800221.806724 ER -