Common Knowledge Semantics of Armstrong’s Axioms

Zachary Heckle and Pavel Naumov

Armstrong's axioms were originally proposed to describe functional dependency between sets of attributes in relational databases. The database semantics of these axioms can be easily rephrased in terms of distributed knowledge in multi-agent systems. The paper proposes alternative semantics of the same axioms in terms of common knowledge. The main technical result of this work is soundness and completeness of Armstrong's axioms with respect to the proposed semantics. An important implication of this result is an unexpected duality between notions of distributed and common knowledge. [pdf]

The Ryoan-ji Axiom for Common Knowledge on Hypergraphs

Jeffrey Kane and Pavel Naumov

The article studies common knowledge in communication networks with a fixed topological structure. It introduces a non-trivial principle, called the Ryoan-ji axiom, which captures logical properties of common knowledge of all protocols with a given network topology. A logical system, consisting of the Ryoan-ji axiom and two additional axioms, is proven to be sound and complete. [pdf]