English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Superposition Decides the First-order Logic Fragment Over Ground Theories

Kruglov, E., & Weidenbach, C. (2012). Superposition Decides the First-order Logic Fragment Over Ground Theories. Mathematics in Computer Science, 6(4), 427-456. doi:10.1007/s11786-012-0135-4.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kruglov, Evgeny1, Author           
Weidenbach, Christoph1, Author           
Affiliations:
1Automation of Logic, MPI for Informatics, Max Planck Society, ou_1116545              

Content

show
hide
Free keywords: -
 Abstract: The hierarchic superposition calculus over a theory T, called SUP(T), enables sound reasoning on the hierarchic combination of a theory T with full first-order logic, FOL(T). If a FOL(T) clause set enjoys a sufficient completeness criterion, the calculus is even complete. Clause sets over the ground fragment of FOL(T) are not sufficiently complete, in general. In this paper we show that any clause set over the ground FOL(T) fragment can be transformed into a sufficiently complete one, and prove that SUP(T) terminates on the transformed clause set, hence constitutes a decision procedure provided the existential fragment of the theory T is decidable. Thanks to the hierarchic design of SUP(T), the decidability result can be extended beyond the ground case. We show SUP(T) is a decision procedure for the non-ground FOL fragment plus a theory T, if every non-constant function symbol from the underlying FOL signature ranges into the sort of the theory T, and every term of the theory sort is ground. Examples for T are in particular decidable fragments of arithmetic.

Details

show
hide
Language(s): eng - English
 Dates: 2012-122012
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/s11786-012-0135-4
BibTex Citekey: KruglovWeidenbachMCS2012
Other: Local-ID: 3AA49DC7DD31016FC1257B1100638146-KruglovWeidenbachMCS2012
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Mathematics in Computer Science
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Basel : Birkhäuser
Pages: - Volume / Issue: 6 (4) Sequence Number: - Start / End Page: 427 - 456 Identifier: ISSN: 1661-8270