University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Cyclic Implicit Complexity

Cyclic Implicit Complexity

Add to your list(s) Download to your calendar using vCal

  • UserAnupam Das, University of Birmingham
  • ClockFriday 11 March 2022, 14:00-15:00
  • HouseFW26.

If you have a question about this talk, please contact Jamie Vicary.

THIS TALK WILL BE IN SS03 , NOT FW26

Circular (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 aspects of circular proofs, which exhibit sophisticated loop structures atypical of more common ‘recursion schemes’. We attempt to bridge the gap between circular proofs and implicit computational complexity. Namely we introduce a circular proof system based on Bellantoni and Cook’s famous safe-normal function algebra, and we identify suitable proof theoretical constraints to characterise the polynomial-time and elementary computable functions.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity