Algebraic Laws for Nondeterminism and Concurrency

Algebraic Laws for Nondeterminism and Concurrency

January 1985 | MATTHEW HENNESSY AND ROBIN MILNER
This paper introduces algebraic laws for nondeterminism and concurrency, focusing on observational equivalence as a way to define program equivalence. The authors propose that two programs are observationally equivalent if they behave the same way for all observers. This concept is formalized through a series of equivalence relations and congruences, which are defined based on how programs interact with their environment. The paper demonstrates that for a sequence of simple languages expressing finite behaviors, observational equivalence can be axiomatized algebraically. With the addition of recursion and other extensions, this algebraic language becomes a tool for writing and specifying concurrent programs and proving their properties. The authors define observational equivalence in terms of how programs communicate with observers. They introduce a framework where the behavior of a program is determined by its observable actions. This leads to a formal definition of observational equivalence, which is shown to be a congruence relation. The paper also provides a logical characterization of observational equivalence, showing that it can be expressed using a modal language. The paper then applies these concepts to a simple nondeterministic language, showing how observational equivalence can be characterized algebraically. It introduces a signature for this language and defines experiment relations that capture the behavior of programs. The authors show that observational congruence can be characterized by a set of axioms, which allow for the derivation of equivalence relations between programs. The paper also discusses the implications of unobservable actions in programs, showing how they affect the observable behavior of programs. It introduces a new observational equivalence relation that accounts for unobservable actions and shows how this relation can be characterized algebraically. Finally, the paper extends the language to include communication between programs, introducing a new binary operator to represent concurrent execution. It shows how this operator affects the behavior of programs and how observational equivalence can be extended to account for communication. The paper concludes by demonstrating that the algebraic laws for nondeterminism and concurrency can be used to define and reason about the behavior of concurrent programs.This paper introduces algebraic laws for nondeterminism and concurrency, focusing on observational equivalence as a way to define program equivalence. The authors propose that two programs are observationally equivalent if they behave the same way for all observers. This concept is formalized through a series of equivalence relations and congruences, which are defined based on how programs interact with their environment. The paper demonstrates that for a sequence of simple languages expressing finite behaviors, observational equivalence can be axiomatized algebraically. With the addition of recursion and other extensions, this algebraic language becomes a tool for writing and specifying concurrent programs and proving their properties. The authors define observational equivalence in terms of how programs communicate with observers. They introduce a framework where the behavior of a program is determined by its observable actions. This leads to a formal definition of observational equivalence, which is shown to be a congruence relation. The paper also provides a logical characterization of observational equivalence, showing that it can be expressed using a modal language. The paper then applies these concepts to a simple nondeterministic language, showing how observational equivalence can be characterized algebraically. It introduces a signature for this language and defines experiment relations that capture the behavior of programs. The authors show that observational congruence can be characterized by a set of axioms, which allow for the derivation of equivalence relations between programs. The paper also discusses the implications of unobservable actions in programs, showing how they affect the observable behavior of programs. It introduces a new observational equivalence relation that accounts for unobservable actions and shows how this relation can be characterized algebraically. Finally, the paper extends the language to include communication between programs, introducing a new binary operator to represent concurrent execution. It shows how this operator affects the behavior of programs and how observational equivalence can be extended to account for communication. The paper concludes by demonstrating that the algebraic laws for nondeterminism and concurrency can be used to define and reason about the behavior of concurrent programs.
Reach us at info@study.space
[slides and audio] Algebraic laws for nondeterminism and concurrency