Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25201
Titel: String unification is essentially infinitary
Verfasser: Hoche, Michael
Siekmann, Jörg
Szabo, Peter
Sprache: Englisch
Erscheinungsjahr: 2008
SWD-Schlagwörter: Künstliche Inteligenz
Freie Schlagwörter: E-unification
equational theory
universal algebra
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: A unifier of two terms s and t is a substitution sigma such that ssigma=tsigma and for first-order terms there exists a most general unifier sigma in the sense that any other unifier delta can be composed from sigma with some substitution lambda, i.e. delta=sigmacirclambda. This notion can be generalised to E-unification , where E is an equational theory, =_{E} is equality under E andsigmaa is an E-unifier if ssigma =_{E}tsigma. Depending on the equational theory E, the set of most general unifiers is always a singleton (as above), or it may have more than one, either finitely or infinitely many unifiers and for some theories it may not even exist, in which case we call the theory of type nullary. String unification (or Löb's problem, Markov's problem, unification of word equations or Makanin's problem as it is often called in the literature) is the E-unification problem, where E = {f(x,f(y,z))=f(f(x,y),z)}, i.e. unification under associativity or string unification once we drop the fs and the brackets. It is well known that this problem is infinitary and decidable. Essential unifiers, as introduced by Hoche and Szabo, generalise the notion of a most general unifier and have a dramatically pleasant effect on the set of most general unifiers: the set of essential unifiers is often much smaller than the set of most general unifiers. Essential unification may even reduce an infinitary theory to an essentially finitary theory. The most dramatic reduction known so far is obtained for idempotent semigroups or bands as they are called in computer science: bands are of type nullary, i.e. there exist two unifiable terms s and t, but the set of most general unifiers is not enumerable. This is in stark contrast to essential unification: the set of essential unifiers for bands always exists and is finite. We show in this paper that the early hope for a similar reduction of unification under associativity is not justified: string unification is essentially infinitary. But we give an enumeration algorithm for essential unifiers. And beyond, this algorithm terminates when the considered problem is finitary.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-42939
hdl:20.500.11880/25257
http://dx.doi.org/10.22028/D291-25201
Schriftenreihe: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Band: 08-01
SciDok-Publikation: 25-Nov-2011
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
RR_08_01.pdf5,36 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.