Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-40102
Titel: Unification in Permutative Equational Theories is Undecidable
VerfasserIn: Schmidt-Schauß, Manfred
Sprache: Englisch
Erscheinungsjahr: 1987
Erscheinungsort: Kaiserslautern
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Forschungsbericht (Report zu Forschungsprojekten)
Abstract: An equational theory E is permutative if in every valid equation s =E t the terms s and t have the same symbols with the same number of occurrences. The class of permutative equational theories includes associativity and commutativity and hence is important for unification theory, for term rewriting systems modulo equational theories and corresponding completion procedures. It is shown in this research note that there is no algorithm that decides E-unifiability of terms for all permutative theories. The proof technique is to provide for every Turing machine M a permutative theory with a confluent term rewriting system such that narrowing on certain terms simulates the Turing machine M.
Link zu diesem Datensatz: urn:nbn:de:bsz:291--ds-401022
hdl:20.500.11880/36223
http://dx.doi.org/10.22028/D291-40102
Schriftenreihe: SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447]
Band: 87,3
Datum des Eintrags: 11-Aug-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-87-03_Schmidt=Schauß_Unification-in-Permutative-Equational-Theories-is-Undecidable.pdf844,49 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.