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öße | Format | |
---|---|---|---|---|
SEKI-Report-SR-87-03_Schmidt=Schauß_Unification-in-Permutative-Equational-Theories-is-Undecidable.pdf | 844,49 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.