Model-checking process equivalences

DOI10.1016/J.TCS.2014.08.020zbMATH Open1303.68085arXiv1210.2451OpenAlexW2034020594MaRDI QIDQ477208FDOQ477208

Authors: Martin Lange, Etienne Lozes, Manuel Vargas Guzmán 

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Process equivalences are formal methods that relate programs and system which, informally, behave in the same way. Since there is no unique notion of what it means for two dynamic systems to display the same behaviour there are a multitude of formal process equivalences, ranging from bisimulation to trace equivalence, categorised in the linear-time branching-time spectrum. We present a logical framework based on an expressive modal fixpoint logic which is capable of defining many process equivalence relations: for each such equivalence there is a fixed formula which is satisfied by a pair of processes if and only if they are equivalent with respect to this relation. We explain how to do model checking, even symbolically, for a significant fragment of this logic that captures many process equivalences. This allows model checking technology to be used for process equivalence checking. We show how partial evaluation can be used to obtain decision procedures for process equivalences from the generic model checking scheme.

Full work available at URL: https://arxiv.org/abs/1210.2451

Recommendations

• Model-checking process equivalences
• Testing equivalences for processes
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Testing equivalence as a bisimulation equivalence
• Modal logics for mobile processes

zbMATH Keywords

model-checkinghigher-order \(\mu\)-calculuspolyadic \(\mu\)-calculusprocess equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
• Title not available (Why is that?)
• Decidability of DPDA equivalence
• CCS expressions, finite state processes, and three problems of equivalence
• Title not available (Why is that?)
• Fair simulation
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Model Checking the First-Order Fragment of Higher-Order Fixpoint Logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Model-checking process equivalences
• The Complexity of Model Checking Higher-Order Fixpoint Logic
• CONCUR 2004 - Concurrency Theory
• Model-checking the higher-dimensional modal \(\mu\)-calculus

Cited In (10)

• Title not available (Why is that?)
• Equivalence checking using structural methods
• Interleaving isotactics -- an equivalence notion on behaviour abstractions
• The arity hierarchy in the polyadic \(\mu\)-calculus
• Model-checking process equivalences
• Encoding safety in \(\mathrm{CLL}_R\)
• Capturing bisimulation-invariant exponential-time complexity classes
• Experimenting with process equivalence
• Process equivalence problems as energy games
• A type-based HFL model checking algorithm

This page was built for publication: Model-checking process equivalences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477208)