Automated Deduction in Classical and Non-Classical Logics

Thisvolumeisacollectionofpapers onautomateddeduction inclassical,modal, and many-valued logics, with an emphasis on rst-order theories. Some authors bridgethe gaptohigher-order logicbydealingwithsimpletype theory ina r- order setting, or by resolving shortcomings of r st-order logic with the help of higher-order notions. Most papers rely on resolution or tableaux methods, with a few exceptions choosing the equational paradigm. In its entirety the volume is a mirror of contemporary research in r st-order theorem proving. One trend to be observed is the interest in e ective decision procedures. The main aim of rs t-order theorem proving was and still is to demonstrate the validity or unsatisa bility of formulas, by more and more - phisticatedmethods. Withinthelastyears,however,theothersideofthemedal{ falsi abilityand satisab ility { has r eceived growing attention. Though in g- eral non-terminating, theorem provers sometimes act as decision procedures on subclasses ofrs t-order logic. Inparticularcases theiroutputcanevenbeused to extract n ite representations of models or counter-examples. Another devel- mentistheextension ofdeductiontechniquesfromclassicallogictomany-valued and modal logics. By suitably generalizing classical concepts many results carry over to non-classical logics. This line of research is stimulated by artici al int- ligence with its need for more expressive logics capable of modeling real-world reasoning. From a formal point of view this volume comprises two types of papers, invited and contributed ones. Gilles Dowek, Melvin Fitting, Deepak Kapur, Alexander Leitsch, and David Plaisted accepted our invitation to present recent developments in and their view of the e ld. Contributed papers on the other hand underwent a two-staged selection process.

Includes supplementary material: sn.pub/extras

Inhalt
Invited Papers.- Automated Theorem Proving in First-Order Logic Modulo: On the Difference between Type Theory and Set Theory.- Higher-Order Modal LogicA Sketch.- Proving Associative-Commutative Termination Using RPO-Compatible Orderings.- Decision Procedures and Model Building or How to Improve Logical Information in Automated Deduction.- Replacement Rules with Definition Detection.- Contributed Papers.- On the Complexity of Finite Sorted Algebras.- A Further and Effective Liberalization of the ?-Rule in Free Variable Semantic Tableaux.- A New Fast Tableau-Based Decision Procedure for an Unquantified Fragment of Set Theory.- Interpretation of a Mizar-Like Logic in First Order Logic.- An ((n · log n)3)-Time Transformation from Grz into Decidable Fragments of Classical First-Order Logic.- Implicational Completeness of Signed Resolution.- An Equational Re-engineering of Set Theories.- Issues of Decidability for Description Logics in the Framework of Resolution.- Extending DecidableClause Classes via Constraints.- Completeness and Redundancy in Constrained Clause Logic.- Effective Properties of Some First Order Intuitionistic Modal Logics.- Hidden Congruent Deduction.- Resolution-Based Theorem Proving for SH n-Logics.- Full First-Order Sequent and Tableau Calculi With Preservation of Solutions and the Liberalized ?-Rule but Without Skolemization.