Completeness and Incompleteness of Trace-Based Network Proof Systems
Widom, Jennifer; Gries, David; Schneider, Fred B.
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.
computer science; technical report
Previously Published As