David Cerna,
"On the Complexity of Unsatisfiable Primitive Recursively defined $\Sigma_1$-Sentences"
: T.B.D., Seite(n) 1--17, 2019
Original Titel:
On the Complexity of Unsatisfiable Primitive Recursively defined $\Sigma_1$-Sentences
Sprache des Titels:
Englisch
Original Buchtitel:
T.B.D.
Original Kurzfassung:
We introduce a measure of complexity based on formula occurrence within instance proofs of an inductive statement. Our measure is closely related to {\em Herbrand Sequent length}, but instead of capturing the number of necessary term instantiations, it captures the finite representational difficulty of a recursive sequence of proofs. We restrict ourselves to a class of unsatisfiable primitive recursively defined negation normal form first-order sentences, referred to as {\em abstract sentences}, which capture many problems of interest; for example, variants of the {\em infinitary pigeonhole principle}. This class of sentences has been particularly useful for inductive formal proof analysis and proof transformation. Together our complexity measure and abstract sentences allow use to capture a notion of {\em tractability} for state-of-the-art approaches to inductive theorem proving, in particular {\em loop discovery} and {\em tree grammar} based inductive theorem provers. We provide a complexity analysis of an important abstract sentence, and discuss the analysis of a few related sentences, based on the infinitary pigeonhole principle which we conjecture represent the upper limits of tractability and foundation of intractability with respect to the current approaches.
Forschungs-