A Logic of Information Flows

A challenge in descriptive complexity is to identify logics with low complexity that simultaneously express both fundamental reachability properties and counting properties on unordered structures. We present a family of logics that allow fine control of the complexity of order-independent computations. The approach is based on adding the ability to reason about information propagations in first-order logic with fixed points. Two parameters may be used to control expressiveness and complexity: the set of definable connectives, and the expressiveness of atomic units. We identify a fragment with polytime data complexity and show that it can express both reachability and counting properties on unordered structures. The fragment is less expressive than FO(FP) both in its FO part and its recursive construct, but is more expressive in its ability to constrain information flows by means of (definable) modalities, similar to Dynamic logic.

Authors

• Eugenia Ternovska.

Keywords

No keywords are indexed for this paper.