Bisimulations and predicate logic
Author:
- 1 September 1994
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 59 (3) , 924-944
Abstract
Elementary (first-order) and nonelementary (set-theoretic) aspects of the largest bisimulation are considered with a view toward analyzing operational semantics from the perspective of predicate logic. The notion of a bisimulation is employed in two distinct ways: (i) as an extensional notion of equivalence on programs (or processes) generalizing input/output equivalence (at a cost exceedingover certain transition predicates computable in log space), and (ii) as a tool for analyzing the dependence of transitions on data (which can be shown to be elementary or nonelementary, depending on the formulation of the transitions).Keywords
This publication has 9 references indexed in Scilit:
- Back and Forth Between Modal Logic and Classical LogicLogic Journal of the IGPL, 1995
- Logic of transition systemsJournal of Logic, Language and Information, 1994
- Comparative transition system semanticsLecture Notes in Computer Science, 1993
- Transition systems and dynamic semantics1992
- A domain equation for bisimulationInformation and Computation, 1991
- Process Algebra1990
- Handbook of Philosophical Logic, Volume II. Extensions of Classical Logic.The Philosophical Quarterly, 1986
- Algebraic laws for nondeterminism and concurrencyJournal of the ACM, 1985
- Admissible Sets and Structures1975