Please use this identifier to cite or link to this item: doi:10.22028/D291-40239
Title: On the Solvability of Equational Problems
Author(s): Bürckert, Hans-Jürgen
Schmidt-Schauß, Manfred
Language: English
Year of Publication: 1989
Place of publication: Kaiserslautern
Free key words: equational theory
equational problem
word problem
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: In this report we present some results on decidability, undecidability, semi-decidability, and non-semi-decidability of general and special equational problems. Solving an equational problem is the task to find out given an equational theory and any first order formula where the equality sign is the only predicate symbol, if this formula is true in the free algebra (or in the initial algebra) of this equational theory. One is usually interested in a constructive proof of an equational problem, i.e., the assignments of existentially quantified variables with elements of this algebra have to be constructed explicitely. Special cases are equality problems, unification and disunification problems: A disunification problem is the problem of solving a system of equations and disequations (i.e. negated equations) in the free or initial algebra of an equational theory, i.e. to prove the existentially closed conjunction of the equations and disequations in this algebra. Assignments for the variables occurring in the system, that make the terms of the equations equal, but let those of the disequations different are called solutions. Unification is as common the problem of solving a system of equations only, the solutions are called unifiers. Equality problems are universally closed equations. We are only interested in the question if there is a decision or at least a semi-decision procedure for the solvability of these problems but not in the task of finding procedures that compute the solutions.
Link to this record: urn:nbn:de:bsz:291--ds-402396
Series name: SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447]
Series volume: 89,7
Date of registration: 14-Aug-2023
Notes: 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.
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Professorship: SE - Sonstige
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
SEKI-Report-SR-89-07_Bürckert-Schmidt=Schauß_On-the-Solvability-of-Equational-Problems.pdf1,49 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.