Cyclic implicit complexity

DOI10.1145/3531130.3533340MaRDI QIDQ6649449zbMATH OpenFDO

Authors Gianluca Curzi, Anupam Das

Publication date 6 December 2024

Full work available at URL https://doi.org/10.1145/3531130.3533340

zbMATH Keywords

safe recursionfunction algebrasimplicit complexitycyclic proofshigher-order complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Structure of proofs (03F07) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 2087442
• Automated Reasoning with Analytic Tableaux and Related Methods
• Circular (yet sound) proofs
• scientific article; zbMATH DE number 7155168
• Circular coinduction: a proof theoretical foundation

Cites work

• scientific article; zbMATH DE number 6680140 (Why is no real title available?)
• scientific article; zbMATH DE number 1223626 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• scientific article; zbMATH DE number 7533344 (Why is no real title available?)
• scientific article; zbMATH DE number 7155168 (Why is no real title available?)
• A Proof System for the Linear Time μ-Calculus
• A cut-free cyclic proof system for Kleene algebra
• A new recursion-theoretic characterization of the polytime functions
• Characterizing PSPACE with pointers
• Cyclic Proofs and Jumping Automata
• Cyclic arithmetic is equivalent to Peano arithmetic
• Equivalence of inductive definitions and cyclic proofs under arithmetic
• Games for the -calculus
• Higher type recursion, ramification and polynomial time
• Infinets: the parallel syntax for non-wellfounded proof-theory
• Infinitary proof theory: the multiplicative additive case
• On the Logical Strength of Confluence and Normalisation for Cyclic Proofs.
• PSPACE-completeness of a thread criterion for circular proofs in linear logic with least and greatest fixed points
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• Sequent calculi for induction and infinite descent
• The logical strength of Büchi's decidability theorem

Cited in

(7)

• A proof theory of right-linear ( -)grammars via cyclic proofs
• A proof theory of ( -)context-free languages, via non-wellfounded proofs
• Cyclic implicit complexity
• Infinitary cut-elimination via finite approximations
• Abstract cyclic proofs
• On the Logical Strength of Confluence and Normalisation for Cyclic Proofs.
• Herbrand schemes for cyclic proofs

This page was built for publication: Cyclic implicit complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6649449)