BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Nikolaos Galatos (University of Denver) DTSTART:20250403T180000Z DTEND:20250403T190000Z DTSTAMP:20260423T021224Z UID:OLS/166 DESCRIPTION:Title: Ti ght complexity bounds for substructural logics\nby Nikolaos Galatos (U niversity of Denver) as part of Online logic seminar\n\n\nAbstract\nSubstr uctural logics constitute generalizations of classical and intuitionistic logic that allow for resource sensitive reasoning\; they connect to philos ophy\, computer science\, engineering\, mathematical linguistics and theor etical physics. Their algebraic semantics\, residuated lattices\, have the ir independent history and relate to ring theory\, lattice-ordered groups and Tarski’s relation algebras\, among other algebraic structures. \n\n We discuss the complexity of provability and of deduciblity of various sub structural logics\, ranging from low complexity classes to undecidability. Of particular interest are certain knotted extensions which have (non-ele mentary) complexity in the Ackermann level of the fast-growing hierarchy. We obtain lower complexity bounds by encoding suitable and-branching count er machines into the corresponding algebraic semantics\, using the method of residuated frames. For the upper bounds\, we undertake a proof-theoreti c investigation of auxiliary analytic calculi and employ methods from the theory of well-ordered sets to obtain length theorems. Together\, these yi eld tight complexity bounds for the logics under investigation. Our result s cover both sequent and hypersequent calculi.\n LOCATION:https://researchseminars.org/talk/OLS/166/ END:VEVENT END:VCALENDAR