Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-40238
Titel: | The Unification Hierarchy is Undecidable |
VerfasserIn: | Nutt, Werner |
Sprache: | Englisch |
Erscheinungsjahr: | 1989 |
Erscheinungsort: | Kaiserslautern |
Freie Schlagwörter: | Equational Theories Matching Unification |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | In unification theory, equational theories can be classified according to the existence and cardinality of minimal complete solution sets for equation systems. For unitary, finitary, and infinitary theories minimal complete solution sets always exist and are singletons, finite, or possibly infinite sets, respectively. In nullary theories, minimal complete sets do not exist for some equation systems. These classes form the unification hierarchy. We show that it is not possible to decide where a given equational theory resides in the unification hierarchy. Moreover, it is proved that for some classes this problem is not even recursively enumerable. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-402384 hdl:20.500.11880/36250 http://dx.doi.org/10.22028/D291-40238 |
Schriftenreihe: | SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447] |
Band: | 89,6 |
Datum des Eintrags: | 14-Aug-2023 |
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-89-06_Nutt_The-Unification-Hierarchy-is-Undecidable.pdf | 4,47 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.