Computational content of circular proof systems

Prelegent(ci)

Denis Kuperberg

Afiliacja

CNRS, LIP, ENS Lyon

Termin

13 maja 2020 14:15

Informacje na temat wydarzenia

Online seminar

Tytuł w języku angielskim

joint work with Laureline Pinault and Damien Pous

Seminarium

Seminarium „Teoria automatów”

---

Cyclic proofs are a class of formal proof systems that allow some kind of circular reasoning. Unlike classical proofs, represented by finite trees with axioms as leaves, cyclic proofs are represented by trees containing infinite branches. The Curry-Howard correspondence allows us to see these cyclic proofs as programs. We investigate the computational content of a cyclic proof system based on Kleene algebra, where we see expressions as data types. Different proofs of the same sequent e |- f can be  interpreted as different programs mapping every input of type e to an output of type f. We show that depending on the particular rules allowed in the system, the computational content of proofs matches different known complexity classes: regular languages, Logspace, primitive recursive functions, system T. Various tools are used to pinpoint these different expressive powers, including a newly introduced class of automata (Jumping Multihead Automata), and results from the field of reverse mathematics.

---