Evgenia (Eugenia) Ternovska
Associate Professor | School of Computing Science
Simon Fraser University 8888 University Dr., Burnaby, B.C. V5A 1S6
13 February 2020, 10:30-11:30
ENS, S16
Logic of Information Flows: Expressing Reachability and Cardinality Properties
A challenge in descriptive complexity is to identify logics with low complexity that simultaneously express fundamental reachability and counting properties on unordered structures. We define 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, FO(FP). Two parameters are used to control expressiveness and complexity: the set of logical connectives and the expressiveness of atomic units. We restrict both and obtain a modal temporal (Dynamic) logic over monadic unions of conjunctive queries. A crucial component is a dynamic version of Hilbert’s Epsilon operator. We identify a fragment with polytime data complexity and show that it can express both reachability and counting properties on unordered structures. Finally, we formalize Epsilon-invariance property for this logic and conjecture its decidability.
