Formal Aspects of Computing · 1992 · 96 citations · 9 references
ComputingComputer ScienceAlgorithmsSystems AnalysisTheory Of ComputationAutomata TheoryComputational ComplexityFinite AutomataFinite State Machine ModelingFinite-state MachinesModel CheckingBisimulationBisimulation AnalysisFinite-state ProcessesFinite-state VerificationReducibilityState Transition SystemsStrong BisimulationTransition Systems
Abstract In 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 NC algorithm to solve any of these problems will require an algorithmic breakthrough, which is exceedingly hard to achieve.
9
Three Partition Refinement Algorithms
Robert Paige, Robert E. Tarjan · SIAM Journal on Computing · 1987 · 1.2K citations
Formal verification of parallel programs
Robert Keller · Communications of the ACM · 1976 · 791 citations · Full text