The Experts below are selected from a list of 4839 Experts worldwide ranked by ideXlab platform
Rajeev Gore - One of the best experts on this subject based on the ideXlab platform.
-
Combining Derivations and Refutations for Cut-free Completeness in Bi-Intuitionistic Logic
Journal of Logic and Computation, 2008Co-Authors: Rajeev Gore, Linda PostnieceAbstract:Bi-Intuitionistic Logic is the union of Intuitionistic and dual Intuitionistic Logic, and was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent ‘cut-free’ sequent calculus has recently been shown to fail cut-elimination. We present a new cut-free sequent calculus for bi-Intuitionistic Logic, and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between Intuitionistic implication and dual Intuitionistic exclusion, similarly to future and past modalities in tense Logic. Our calculus handles this interaction using derivations and refutations as first class citizens. We employ extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of refutations, and rules which compose certain refutations and derivations to form derivations. Automated deduction using terminating backward search is also possible, although this is not our main purpose.
-
a cut free sequent calculus for bi Intuitionistic Logic
Theorem Proving with Analytic Tableaux and Related Methods, 2007Co-Authors: Linda Buisman, Rajeev GoreAbstract:Bi-Intuitionistic Logic is the extension of Intuitionistic Logic with a connective dual to implication. Bi-Intuitionistic Logic was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent "cut-free" sequent calculus for BiInt has recently been shown by Uustalu to fail cut-elimination. We present a new cut-free sequent calculus for BiInt , and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between implication and its dual, similarly to future and past modalities in tense Logic. Our calculus handles this interaction using extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of failed derivation trees. Our simple termination argument allows our calculus to be used for automated deduction, although this is not its main purpose.
-
A Cut-free Sequent Calculus for Bi-Intuitionistic Logic: Extended Version
arXiv: Logic in Computer Science, 2007Co-Authors: Linda Buisman, Rajeev GoreAbstract:Bi-Intuitionistic Logic is the extension of Intuitionistic Logic with a connective dual to implication. Bi-Intuitionistic Logic was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent ``cut-free'' sequent calculus for BiInt has recently been shown by Uustalu to fail cut-elimination. We present a new cut-free sequent calculus for BiInt, and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between implication and its dual, similarly to future and past modalities in tense Logic. Our calculus handles this interaction using extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of failed derivation trees. Our simple termination argument allows our calculus to be used for automated deduction, although this is not its main purpose.
-
TABLEAUX - A Cut-Free Sequent Calculus for Bi-Intuitionistic Logic
Lecture Notes in Computer Science, 2007Co-Authors: Linda Buisman, Rajeev GoreAbstract:Bi-Intuitionistic Logic is the extension of Intuitionistic Logic with a connective dual to implication. Bi-Intuitionistic Logic was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent "cut-free" sequent calculus for BiInt has recently been shown by Uustalu to fail cut-elimination. We present a new cut-free sequent calculus for BiInt , and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between implication and its dual, similarly to future and past modalities in tense Logic. Our calculus handles this interaction using extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of failed derivation trees. Our simple termination argument allows our calculus to be used for automated deduction, although this is not its main purpose.
-
dual Intuitionistic Logic revisited
Theorem Proving with Analytic Tableaux and Related Methods, 2000Co-Authors: Rajeev GoreAbstract:We unify the algebraic, relational and sequent methods used by various authors to investigate “dual Intuitionistic Logic”. We show that restricting sequents to “singletons on the left/right” cannot capture “Intuitionistic Logic with dual operators”, the natural hybrid Logic that arises from Intuitionistic and dual-Intuitionistic Logic. We show that a previously reported generalised display framework does deliver the required cut-free display calculus. We also pinpoint precisely the structural rule necessary to turn this display calculus into one for classical Logic.
Andrei Voronkov - One of the best experts on this subject based on the ideXlab platform.
-
Proof-Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification
Journal of Automated Reasoning, 2003Co-Authors: Andrei VoronkovAbstract:We characterize provability in Intuitionistic Logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in Intuitionistic Logic with equality and solutions to simultaneous rigid E -unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E -unifiability. This gives us a proof procedure for Intuitionistic Logic with equality modulo simultaneous rigid E -unification. We also show that simultaneous rigid E -unifiability is polynomial-time reducible to Intuitionistic Logic with equality. Thus, any proof procedure for Intuitionistic Logic with equality can be considered as a procedure for simultaneous rigid E -unifiability. In turn, any procedure for simultaneous rigid E -unifiability gives a procedure for establishing provability in Intuitionistic Logic with equality.
-
Proof Search in Intuitionistic Logic with Equality, or Back toSimultaneous Rigid E -Unification
Journal of Automated Reasoning, 1998Co-Authors: Andrei VoronkovAbstract:We characterize provability in Intuitionistic Logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in Intuitionistic Logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for Intuitionistic Logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to Intuitionistic Logic with equality. Thus, any proof procedure for Intuitionistic Logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in Intuitionistic Logic with equality.
-
CADE - Proof-Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification
Automated Deduction — Cade-13, 1996Co-Authors: Andrei VoronkovAbstract:We characterize provability in Intuitionistic Logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in Intuitionistic Logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for Intuitionistic Logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to Intuitionistic Logic with equality. Thus, any proof procedure for Intuitionistic Logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in Intuitionistic Logic with equality.
-
LICS - Decidability problems for the prenex fragment of Intuitionistic Logic
Proceedings 11th Annual IEEE Symposium on Logic in Computer Science, 1Co-Authors: Anatoli Degtyarev, Andrei VoronkovAbstract:We develop a constraint-based technique which allows one to prove decidability and complexity results for sequent calculi. Specifically, we study decidability problems for the prenex fragment of Intuitionistic Logic. We introduce an analogue of Skolemization for Intuitionistic Logic with equality, prove PSPACE-completeness of two fragments of Intuitionistic Logic with and without equality and some other results. In the proofs, we use a combination of techniques of constraint satisfaction, loop-free sequent systems of Intuitionistic Logic and properties of simultaneous rigid E-unification.
Oliver Bittel - One of the best experts on this subject based on the ideXlab platform.
-
JELIA - Tableau-Based Theorem Proving and Synthesis of Lambda-Terms in the Intuitionistic Logic
Lecture Notes in Computer Science, 1992Co-Authors: Oliver BittelAbstract:Because of its constructive aspect, the Intuitionistic Logic plays an important role in the context of the programming paradigm ”programming by proving”. Programs are expressed by λ-terms which can be seen as compact representations of natural deduction proofs. We are presenting a tableau calculus for the first-order Intuitionistic Logic which allows to synthesize λ-terms. The calculus is obtained from the tableau calculus for the classical Logic by extending its rules by λ-terms. In each rule application and closing of tableau branches, λ-terms are synthesized by unification. Particularly, a new λ-term construct (implicit case analysis) is introduced for the the disjunction rules.
Martin Mundhenk - One of the best experts on this subject based on the ideXlab platform.
-
The model checking problem for propositional Intuitionistic Logic with one variable is AC^1-complete
2011Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the model checking problem for propositional Intuitionistic Logic. We show that the model checking problem for Intuitionistic Logic with one variable is complete for logspace-uniform AC^1, and for Intuitionistic Logic with two variables it is P-complete. For superIntuitionistic Logics with one variable, we obtain NC^1-completeness for the model checking problem and for the tautology problem.
-
the model checking problem for propositional Intuitionistic Logic with one variable is ac 1 complete
Symposium on Theoretical Aspects of Computer Science, 2011Co-Authors: Martin Mundhenk, Felix WeisAbstract:We investigate the complexity of the model checking problem for propositional Intuitionistic Logic. We show that the model checking problem for Intuitionistic Logic with one variable is complete for logspace-uniform AC 1 , and for Intuitionistic Logic with two variables it is P-complete. For superIntuitionistic Logics with one variable, we obtain NC 1 -completeness for the model checking problem and for the tautology problem. 1998 ACM Subject Classification F.2 Analysis of algorithms and problem complexity, F.4 Mathematical Logic and formal languages
-
STACS - The model checking problem for propositional Intuitionistic Logic with one variable is AC 1 -complete
2011Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the model checking problem for propositional Intuitionistic Logic. We show that the model checking problem for Intuitionistic Logic with one variable is complete for logspace-uniform AC 1 , and for Intuitionistic Logic with two variables it is P-complete. For superIntuitionistic Logics with one variable, we obtain NC 1 -completeness for the model checking problem and for the tautology problem. 1998 ACM Subject Classification F.2 Analysis of algorithms and problem complexity, F.4 Mathematical Logic and formal languages
-
The Model Checking Problem for Propositional Intuitionistic Logic with One Variable is AC1-Complete
arXiv: Computational Complexity, 2010Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the model checking problem for propositional Intuitionistic Logic. We show that the model checking problem for Intuitionistic Logic with one variable is complete for logspace-uniform AC1, and for Intuitionistic Logic with two variables it is P-complete. For superIntuitionistic Logics with one variable, we obtain NC1-completeness for the model checking problem and for the tautology problem.
Juan Manuel Cornejo - One of the best experts on this subject based on the ideXlab platform.
-
Proofs of some Propositions of the semi-Intuitionistic Logic with Strong Negation
2017Co-Authors: Juan Manuel Cornejo, Ignacio D. ViglizzoAbstract:We offer the proofs that complete our article introducing the propositional calculus called semi-Intuitionistic Logic with strong negation.
-
Semi-Intuitionistic Logic with Strong Negation
Studia Logica, 2017Co-Authors: Juan Manuel Cornejo, Ignacio D. ViglizzoAbstract:Motivated by the definition of semi-Nelson algebras, a propositional calculus called semi-Intuitionistic Logic with strong negation is introduced and proved to be complete with respect to that class of algebras. An axiomatic extension is proved to have as algebraic semantics the class of Nelson algebras.
-
Gentzen-Style Sequent Calculus for Semi-Intuitionistic Logic
Studia Logica, 2016Co-Authors: Diego Castaño, Juan Manuel CornejoAbstract:The variety \({\mathcal{SH}}\) of semi-Heyting algebras was introduced by H. P. Sankappanavar (in: Proceedings of the 9th “Dr. Antonio A. R. Monteiro” Congress, Universidad Nacional del Sur, Bahia Blanca, 2008) [13] as an abstraction of the variety of Heyting algebras. Semi-Heyting algebras are the algebraic models for a Logic HsH, known as semi-Intuitionistic Logic, which is equivalent to the one defined by a Hilbert style calculus in Cornejo (Studia Logica 98(1–2):9–25, 2011) [6]. In this article we introduce a Gentzen style sequent calculus GsH for the semi-Intuitionistic Logic whose associated Logic GsH is the same as HsH. The advantage of this presentation of the Logic is that we can prove a cut-elimination theorem for GsH that allows us to prove the decidability of the Logic. As a direct consequence, we also obtain the decidability of the equational theory of semi-Heyting algebras.
-
Semi-Intuitionistic Logic
Studia Logica, 2011Co-Authors: Juan Manuel CornejoAbstract:The purpose of this paper is to define a new Logic $${\mathcal {SI}}$$ called semi-Intuitionistic Logic such that the semi-Heyting algebras introduced in [4] by Sankappanavar are the semantics for $${\mathcal {SI}}$$ . Besides, the Intuitionistic Logic will be an axiomatic extension of $${\mathcal {SI}}$$ .
