Events at The University of Manchester
  • University home
  • Events
  • Home
  • Exhibitions
  • Conferences
  • Lectures and seminars
  • Performances
  • Events for prospective students
  • Sustainability events
  • Family events
  • All Events

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
See travel and contact information
Add to your calendar

More information

  • Department of Mathematics

Other events

  • In category "Seminar"
  • In group "(Maths) Maths seminar series"
  • In group "(Maths) Logic"
  • By Department of Mathematics

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

 

Contact us

  • +44 (0) 161 306 6000

Find us

The University of Manchester
Oxford Rd
Manchester
M13 9PL
UK

Connect with the University

  • Facebook page for The University of Manchester
  • X (formerly Twitter) page for The University of Manchester
  • YouTube page for The University of Manchester
  • Instagram page for The University of Manchester
  • TikTok page for The University of Manchester
  • LinkedIn page for The University of Manchester

  • Privacy /
  • Copyright notice /
  • Accessibility /
  • Freedom of information /
  • Charitable status /
  • Royal Charter Number: RC000797
  • Close menu
  • Home
    • Featured events
    • Today's events
    • The Whitworth events
    • Manchester Museum events
    • Jodrell Bank Discovery Centre events
    • Martin Harris Centre events
    • The John Rylands Library events
    • Exhibitions
    • Conferences
    • Lectures and seminars
    • Performances
    • Events for prospective students
    • Sustainability events
    • Family events
    • All events