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öße | Format | |
---|---|---|---|---|
SEKI-REPORT-SR-86-08_Schmidt-Schauß_Some-Undecidable-Classes-of-Clause-Sets.pdf | 3,41 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.