dc.contributor
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor
Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
dc.contributor
Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author
Balcázar Navarro, José Luis
dc.contributor.author
Gabarró Vallès, Joaquim
dc.contributor.author
Santha, Miklos
dc.identifier
Balcazar, J.L.; Gabarro, J.; Santha, M. Deciding bisimilarity is P-complete. 1990.
dc.identifier
https://hdl.handle.net/2117/327610
dc.description.abstract
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.
dc.description.abstract
Postprint (published version)
dc.format
application/pdf
dc.rights
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.rights
Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.subject
Àrees temàtiques de la UPC::Informàtica
dc.subject
Modality (Logic)
dc.subject
P-completeness
dc.subject
many-one NC-reductions
dc.subject
Modalitat (Lògica)
dc.title
Deciding bisimilarity is P-complete
dc.type
External research report
