Researcher profile

David Cerna

David Cerna contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Logic in Computer Science math.LO

Trust snapshot

Quick read

Trust 15 - Baseline

3works

0followers

2topics

2close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Schematic Refutations of Formula Schemata

Proof schemata are infinite sequences of proofs which are defined inductively. In this paper we present a general framework for schemata of terms, formulas and unifiers and define a resolution calculus for schemata of quantifier-free formulas. The new calculus generalizes and improves former approaches to schematic deduction. As an application of the method we present a schematic refutation formalizing a proof of a weak form of the pigeon hole principle.

preprint2016arXiv

Schematic Cut elimination and the Ordered Pigeonhole Principle [Extended Version]

In previous work, an attempt was made to apply the schematic CERES method [8] to a formal proof with an arbitrary number of Π 2 cuts (a recursive proof encapsulating the infinitary pigeonhole principle) [5]. However the derived schematic refutation for the characteristic clause set of the proof could not be expressed in the formal language provided in [8]. Without this formalization a Herbrand system cannot be algorithmically extracted. In this work, we provide a restriction of the proof found in [5], the ECA-schema (Eventually Constant Assertion), or ordered infinitary pigeonhole principle, whose analysis can be completely carried out in the framework of [8], this is the first time the framework is used for proof analysis. From the refutation of the clause set and a substitution schema we construct a Herbrand system.

preprint2015arXiv

Analysis of Clause set Schema Aided by Automated Theorem Proving: A Case Study [Extended Paper]

The schematic CERES method [8] is a recently developed method of cut elimination for proof schemata, that is a sequence of proofs with a recursive construction. Proof schemata can be thought of as a way to circumvent adding an induction rule to the LK-calculus. In this work, we formalize a schematic version of the infinitary pigeonhole principle, which we call the Non-injectivity Assertion schema (NiA-schema), in the LKS-calculus [8], and analyse the clause set schema extracted from the NiA-schema using some of the structure provided by the schematic CERES method. To the best of our knowledge, this is the first appli- cation of the constructs built for proof analysis of proof schemata to a mathematical argument since its publication. We discuss the role of Automated Theorem Proving (ATP) in schematic proof analysis, as well as the shortcomings of the schematic CERES method concerning the formalization of the NiA-schema, namely, the expressive power of the schematic resolution calculus. We conclude with a discussion concerning the usage of ATP in schematic proof analysis.