Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-39819
Titel: Some Undecidable Classes of Clause Sets
VerfasserIn: Schmidt-Schauß, Manfred
Sprache: Englisch
Erscheinungsjahr: 1986
Erscheinungsort: Kaiserslautern
Freie Schlagwörter: Undecidability
Clause sets
Implication of Clauses
Declarations
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Forschungsbericht (Report zu Forschungsprojekten)
Abstract: The undecidability of finitely generated stable transitive relations on free terms is proved in an elementary way and then used to show the undecidability of the implication A => B of two clauses A and B. The implication is decidable in the case A has at most two literals that are complementary unifiable after renaming. Application of the undecidability of transitive relations yields more classes of clause sets that have an undecidable satisfiability problem: clause sets consisting of two clauses with two literals each (2-clauses) and in addition 2 ground units, clause sets consisting of a single 3-clause and arbitrarily many (non-ground) units and clause sets consisting of a 4-clause and arbitrarily many ground units. Finally we show the undecidability of the so-called D-clause sets, where a D-clause is a Horn-clause of the form Q1(x1)^ . . .^ Qn(xn) => Qn+1(t).
Link zu diesem Datensatz: urn:nbn:de:bsz:291--ds-398198
hdl:20.500.11880/36008
http://dx.doi.org/10.22028/D291-39819
Schriftenreihe: SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447]
Band: 86,8
Datum des Eintrags: 21-Jun-2023
Bemerkung/Hinweis: In der GND existiert kein Normdatensatz für die Person, die sie eindeutig als solche identifiziert. Alternative oder damit in Verbindung stehende Schreibweise(n): Schmidt-Schauss, Manfred.
Fakultät: SE - Sonstige Einrichtungen
Fachrichtung: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Professur: SE - Sonstige
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
SEKI-REPORT-SR-86-08_Schmidt-Schauß_Some-Undecidable-Classes-of-Clause-Sets.pdf3,41 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.