• Treffer 94 von 95
Zurück zur Trefferliste

An algorithm for distributive unification

  • We consider unification of terms under the equational theory of two-sided distributivity D with the axioms x*(y+z) = x*y + x*z and (x+y)*z = x*z + y*z. The main result of this paper is that Dunification is decidable by giving a non-deterministic transformation algorithm. The generated unification are: an AC1-problem with linear constant restrictions and a second-order unification problem that can be transformed into a word-unification problem that can be decided using Makanin's algorithm. This solves an open problem in the field of unification. Furthermore it is shown that the word-problem can be decided in polynomial time, hence D-matching is NP-complete.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Manfred Schmidt-SchaußORCiDGND
URN:urn:nbn:de:hebis:30-8891
URL:http://www.ki.informatik.uni-frankfurt.de/papers/schauss/DUNI.ps
Titel des übergeordneten Werkes (Englisch):Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik ; 2
Titel des übergeordneten Werkes (Deutsch):Universität Frankfurt am Main. Fachbereich Informatik: Interner Bericht ; 94,13
Schriftenreihe (Bandnummer):Interner Bericht / Fachbereich Informatik, Johann Wolfgang Goethe-Universität Frankfurt a.M. (94,13)
Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik (2)
Verlag:Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik, Research group for Artificial Intelligence and Software Technology
Verlagsort:Frankfurt [am Main]
Dokumentart:Arbeitspapier
Sprache:Englisch
Jahr der Fertigstellung:1994
Jahr der Erstveröffentlichung:1994
Veröffentlichende Institution:Universitätsbibliothek Johann Christian Senckenberg
Datum der Freischaltung:12.05.2005
Quelle:Internal report 13/94
HeBIS-PPN:190084987
Institute:Informatik und Mathematik / Informatik
DDC-Klassifikation:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Lizenz (Deutsch):License LogoDeutsches Urheberrecht