JavaScript is disabled for your browser. Some features of this site may not work without it.
Completeness and Incompleteness of Trace-Based Network Proof Systems

Author
Widom, Jennifer; Gries, David; Schneider, Fred B.
Abstract
Most trace-based proof systems for networks of processes are known to be incomplete. Extensions to achieve completeness are generally complicated and cumbersome. In this paper, a simple trace logic is defined and two examples are presented to show its inherent incompleteness. Surprisingly, both examples consist of only one process, indicating that network composition is not a cause of incompleteness. Axioms necessary and sufficient for the relative completeness of a trace logic are then presented.
Date Issued
1986-07Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-766
Type
technical report