Fluted Logic with Counting

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Fluted Logic with Counting

Vortrag von Ian Pratt-Hartmann
The fluted fragment is a fragment of first-order logic in which the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that the fluted fragment possesses the finite model property. In this talk, we extend the fluted fragment by the addition of counting quantifiers. We show that the resulting logic retains the finite model property, and that the satisfiability problem for its (m+1)-variable sub-fragment is in m-NExpTime for all positive m. We also consider the satisfiability and finite satisfiability problems for the extension of any of these fragments in which the fluting requirement applies only to sub-formulas having at least three free variables.

This talk is based on the speakers paper Fluted Logic with Counting accepted at ICALP 2021.

Short bio: Ian Pratt-Hartmann studied mathematics and philosophy at Brasenose College, Oxford, and philosophy at Princeton and Stanford Universities, gaining his PhD. from Princeton. He is currently Senior Lecturer in the Department of Computer Science at the University of Manchester. Since February, 2014, Dr. Pratt-Hartmann has held a joint appointment in the Institute of Computer Science at the University of Opole. His academic interests range widely over computational logic, natural language semantics and artificial intelligence.

This talk will take place online via BigBlueButton. To access the room, take one of the following links:

with ZIH-login:


without ZIH-login: