Proof search strategies in linear logic

AAAI Conferences

Linear logic is a refinement of classical logic introduced by J.-Y.Girard to provide means for keeping track of "resources" - two assumptions of a formula A are distinguished from a single assumption of A. Although linear logic is not the first attempt for developing "resourceoriented" logics (relevance logic and Lambek calculus being well-known examples), it is by now the mostinvestigated one. Since its introduction linear logic has enjoyed increasing attention both from proof theorists and computer scientists. The multiplicative fragment of linear logic is claimed to be a system of communication without problems of synchronization. In addition to possible applications to parallelism, linear logic can be seen as a formalism for sharing analysis (with another teminology, also the problem of storage reuse, in-place update, etc) and strictness analysis, two important research areas in functional programming community. In this paper (for details see the full version: [Tammet 93]) we will concentrate on problems of automated theorem proving in full propositional first-order linear logic. We will investigate general search strategies and ways for modifying standard deduction rules in linear logic to make it more suitable for automated proof search, both for "top-down" and "bottom-up" directions. The presented modifications are motivated by experiments performed with our theorem prover. We will describe the implementations and performed experiments for both search directions.


Automating Agential Reasoning: Proof-Calculi and Syntactic Decidability for STIT Logics

arXiv.org Artificial Intelligence

This work provides proof-search algorithms and automated counter-model extraction for a class of STIT logics. With this, we answer an open problem concerning syntactic decision procedures and cut-free calculi for STIT logics. A new class of cut-free complete labelled sequent calculi G3LdmL^m_n, for multi-agent STIT with at most n-many choices, is introduced. We refine the calculi G3LdmL^m_n through the use of propagation rules and demonstrate the admissibility of their structural rules, resulting in auxiliary calculi Ldm^m_nL. In the single-agent case, we show that the refined calculi Ldm^m_nL derive theorems within a restricted class of (forestlike) sequents, allowing us to provide proof-search algorithms that decide single-agent STIT logics. We prove that the proof-search algorithms are correct and terminate.


Classical AI Planning as Theorem Proving: Fragment of Linear Logic

AAAI Conferences

"Fhis pal)er at.tempts to evaluate tile use of a t.heorem prover in the multiplicative fragmeut of linear logic which has been shown t.o simulate conjunctive STRxPs-like planning [9]. A proof search procedure is presented that is correct., complete and only generates lit,ear proofs (i.e.


Towards an efficient prover for the C1 paraconsistent logic

arXiv.org Artificial Intelligence

The KE inference system is a tableau method developed by Marco Mondadori which was presented as an improvement, in the computational efficiency sense, over Analytic Tableaux. In the literature, there is no description of a theorem prover based on the KE method for the C1 paraconsistent logic. Paraconsistent logics have several applications, such as in robot control and medicine. These applications could benefit from the existence of such a prover. We present a sound and complete KE system for C1, an informal specification of a strategy for the C1 prover as well as problem families that can be used to evaluate provers for C1. The C1 KE system and the strategy described in this paper will be used to implement a KE based prover for C1, which will be useful for those who study and apply paraconsistent logics.


Full First-Order Sequent and Tableau Calculi With Preservation of Solutions and the Liberalized delta-Rule but Without Skolemization

arXiv.org Artificial Intelligence

We present a combination of raising, explicit variable dependency representation, the liberalized delta-rule, and preservation of solutions for first-order deductive theorem proving. Our main motivation is to provide the foundation for our work on inductive theorem proving, where the preservation of solutions is indispensable.