Logic seminar: Ian Pratt-Hartmann
| Dates: | 28 February 2024 |
|---|
| Times: | 15:15 - 16:30 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Adults, Alumni, Current University students |
|---|
|
Title: The adjacent fragment of first-order logic---and an excursion into word combinatorics
Abstract: The adjacent fragment is a fragment of first-order logic in which the sequences of variables appearing in atomic subformulas are subject to the constraint that the indices of neighbouring variables differ by no more than 1. This fragment properly subsumes other fragments defined in terms of permitted variable sequences, such as W.V.O. Quine's fluted fragment and A. Herzig's forward fragment. The fluted fragment in turn subsumes multi-modal propositional logic (under the standard first-order translation) as well as a variety of terminological (description) logics.
It was recently shown that the adjacent fragment possesses the finite model property, and that the satisfiability problem for its 2k-variable subfragment is k-NExptime-hard and in (2k-2)-NExpTime. The proof of this fact relies on a surprising---and apparently novel---result in word combinatorics, which may be of interest in its own right. In this talk, I shall describe the adjacent fragment and sketch a proof of the finite model property, including a brief excursion into the world of word combinatorics.
Travel and Contact Information
Find event
Frank Adams 1 (and zoom, link in email)
Alan Turing Building
Manchester
