BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cyclic Implicit Complexity - Anupam Das\, University of Birmingham
DTSTART:20220311T140000Z
DTEND:20220311T150000Z
UID:TALK165310@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION:*THIS TALK WILL BE IN SS03\, NOT FW26*\n\nCircular (or cyclic)
  proofs have received increasing attention in recent years\, and have been
  proposed as an alternative setting for studying (co)inductive reasoning. 
 In particular\, now several type systems based on circular reasoning have 
 been proposed. However\, little is known about the complexity theoretic as
 pects of circular proofs\, which exhibit sophisticated loop structures aty
 pical of more common 'recursion schemes'. We attempt to bridge the gap bet
 ween circular proofs and implicit computational complexity. Namely we intr
 oduce a circular proof system based on Bellantoni and Cook's famous safe-n
 ormal function algebra\, and we identify suitable proof theoretical constr
 aints to characterise the polynomial-time and elementary computable functi
 ons.
LOCATION:FW26
END:VEVENT
END:VCALENDAR