BEGIN:VCALENDAR
PRODID:-//Columba Systems Ltd//NONSGML CPNG/SpringViewer/ICal Output/3.3-
M3//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
DTSTAMP:20240213T102615Z
DTSTART:20240228T151500Z
DTEND:20240228T163000Z
SUMMARY:Logic seminar: Ian Pratt-Hartmann
UID:{http://www.columbasystems.com/customers/uom/gpp/eventid/}b2ty-lsk7x2
of-hnk4oe
DESCRIPTION:Title: The adjacent fragment of first-order logic---and an ex
cursion into word combinatorics\n\nAbstract: The adjacent fragment is a
fragment of first-order logic in which the sequences of variables appear
ing in atomic subformulas are subject to the constraint that the indices
of neighbouring variables differ by no more than 1. This fragment prop
erly subsumes other fragments defined in terms of permitted variable
sequences\, such as W.V.O. Quine's fluted fragment and A. Her
zig's forward fragment. The fluted fragment in turn subsumes mul
ti-modal propositional logic (under the standard first-order translatio
n) as well as a variety of terminological (description) logics.\n\n \n\n
It was recently shown that the adjacent fragment possesses the finite mo
del property\, and that the satisfiability problem for its 2k-variable s
ubfragment is k-NExptime-hard and in (2k-2)-NExpTime. The proof of this
fact relies on a surprising---and apparently novel---result in word comb
inatorics\, 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 mo
del property\, including a brief excursion into the world of word combin
atorics.
STATUS:TENTATIVE
TRANSP:TRANSPARENT
CLASS:PUBLIC
LOCATION:Frank Adams 1 (and zoom\, link in email)\, Alan Turing Building\
, Manchester
END:VEVENT
END:VCALENDAR