Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
ON SKOLEMIZATION AND PROOF COMPLEXITY
View through CrossRef
The impact of Skolemization on the complexity of proofs in the sequent calculus is investigated. It is shown that prefix Skolemization may result in a nonelementary increase of Herbrand complexity (i. e. the minimal number of constituents in a Herbrand disjunction) versus structural Skolemization. Moreover it is shown that restricting the range of quantifiers never increases Herbrand complexity. The results provide a general mathematical justification for minimizing the range of quantifiers (by means of shifting) before Skolemization of formulas.
Title: ON SKOLEMIZATION AND PROOF COMPLEXITY
Description:
The impact of Skolemization on the complexity of proofs in the sequent calculus is investigated.
It is shown that prefix Skolemization may result in a nonelementary increase of Herbrand complexity (i.
e.
the minimal number of constituents in a Herbrand disjunction) versus structural Skolemization.
Moreover it is shown that restricting the range of quantifiers never increases Herbrand complexity.
The results provide a general mathematical justification for minimizing the range of quantifiers (by means of shifting) before Skolemization of formulas.
Related Results
Complexity Theory
Complexity Theory
The workshop
Complexity Theory
was organised by Joachim von zur Gathen (Bonn), Oded Goldreich (Rehovot), Claus-Peter Schnorr (Frankfurt), an...
Transport Layer Security 1.0 handshake protocol formal verification case study: How to use a proof script generator for existing large proof scores
Transport Layer Security 1.0 handshake protocol formal verification case study: How to use a proof script generator for existing large proof scores
The Transport Layer Security (TLS) 1.0 protocol has been formally verified with CafeInMaude Proof Generator (CiMPG) and Proof Assistant (CiMPA), where CafeInMaude is the second maj...
A Generic Deskolemization Strategy
A Generic Deskolemization Strategy
In this paper, we present a general strategy that enables the translation of tableau proofs using different Skolemization rules into machine-checkable proofs. It is part of a frame...
On free proof and regulated proof
On free proof and regulated proof
Free proof and regulated proof are two basic modes of judicial proof. The system of ‘legal proof’ established in France in the 16th century is a classical model of regulated proof....
Development of ACERA Learning Model Based on Proof Construction Analysis
Development of ACERA Learning Model Based on Proof Construction Analysis
Proof constructing is the process of justifying a claim using the methods and concepts of proof to produce mathematical proof. Proof constructing is also an aspect of proof, and is...
Linguistic Complexity
Linguistic Complexity
Linguistic complexity (or: language complexity, complexity in language) is a multifaceted and multidimensional research area that has been booming since the early 2000s. The curren...
(Invited) A 1-mG MEMS Sensor
(Invited) A 1-mG MEMS Sensor
MEMS (microelectromechanical systems) technology has contributed substantially to the miniaturization of inertial sensors, such as accelerometers and gyroscopes [1]. Nowadays, MEMS...
Complexity Theory
Complexity Theory
The workshop
Complexity Theory
was organized by Joachim von zur Gathen (Universität Bonn), Oded Goldreich (Weizmann Institute), and Madhu Su...