Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  AE-Equational theory of context unification is Co-RE-Hard

Vorobyov, S.(1998). AE-Equational theory of context unification is Co-RE-Hard (MPI-I-1998-2-008). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-7A87-8 Versions-Permalink: https://hdl.handle.net/21.11116/0000-0001-7551-0
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-98-2-008.pdf (beliebiger Volltext), 289KB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/21.11116/0000-0001-7552-F
Name:
MPI-I-98-2-008.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Vorobyov, Sergei1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Context unification is a particular case of second-order unification, where all second-order variables are *unary* and only *linear* functions are sought for as solutions. Its decidability is an open problem. We present the simplest (currently known) undecidable quantified fragment of the theory of context unification by showing that for every signature containing a non-unary function symbol there exists a one-parametric context equation such that the universal-existential closure of this equation forms a co-r.e. hard set, as the parameter runs over the set of finite words of a binary alphabet. Moreover, the universal prefix contains one first-order, and the existential prefix contains just 5 context and 3 first-order variables. It follows, in particular, that the AE-equational theory of context unification is undecidable.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1998
 Publikationsstatus: Erschienen
 Seiten: 20 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-1998-2-008
BibTex Citekey: Vorobyov98-2-008
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -