2026-04-17T16:10:01Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/3276102025-07-17T03:45:08Zcom_2072_1033col_2072_452950

Deciding bisimilarity is P-complete Balcázar Navarro, José Luis Gabarró Vallès, Joaquim Santha, Miklos Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals Àrees temàtiques de la UPC::Informàtica Modality (Logic) CCS Bisimilarity P-completeness many-one NC-reductions Modalitat (Lògica) On finite labelled transition systems, the problems of deciding strong bisimilarity, observation equivalence, and observation congruence are P-complete under many-one NC-reducibility. As a consequence, algorithms for automated analysis of finite state systems based on bisimulation seem to be inherently sequential in the following sense: the design of an efficient parallel algorithm to solve any of these problems will require an exceedingly hard algorithmic breakthrough. Postprint (published version) 1990 External research report Balcazar, J.L.; Gabarro, J.; Santha, M. Deciding bisimilarity is P-complete. 1990. https://hdl.handle.net/2117/327610 eng LSI-90-25 http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access Attribution-NonCommercial-NoDerivs 3.0 Spain 16 p. application/pdf