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