A Synchronization Logic: Axiomatics and FormalSemantics of Generalized Horn Clauses

An extension of Horn clause logic is defined based on the introduction of a synchronization operator. Generalized Horn clauses (GHC) are introduced through an informal description of their operational semantics, which allows discussion of some typical synchronization problems. GHC are first considered formally as a programming language by defining the syntax, the operational semantics, the model-theoretic semantics, and the fixed-point semantics. The above mentioned semantics are given in the Van Emden-Kowalski style (1976, J. Assoc. Comput. Mach. 23, 733–742) and are proved equivalent. GHC are then characterized as axiomatic theories. A set of axiom schemata concerned with the newly introduced synchronization operator is defined and it is proved that the operational semantics inference rule is both sound and complete. Finally, the relation between GHC and Horn clauses is analyzed, and it is proved that Horn clause logic is strictly included in the generalized Horn clause logic.