Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  $\forall\exists^\ast$-Equational Theory of Context Unification is $\Pi_1^0$-Hard

Vorobyov, S. (1998). $\forall\exists^\ast$-Equational Theory of Context Unification is $\Pi_1^0$-Hard. In L. Brim, J. Gruska, & J. Zlatuska (Eds.), Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS-98) (pp. 597-606). Berlin, Germany: Springer.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
paper80.ps (beliebiger Volltext), 178KB
 
Datei-Permalink:
-
Name:
paper80.ps
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/postscript
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Vorobyov, Sergei1, 2, Autor           
Affiliations:
1Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046              
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: \begin{abstract} Context unification is a particular case of second-order unification, where all second-order variables are \emph{unary} and only \emph{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 \emph{context unification} by showing that for every signature containing a $\geq\!2$-ary symbol one can construct a \emph{context equation} ${\mathcal E}\,(p,r,\overline{F},\overline{w})$ with parameter $p$, first-order variables $r$, $\overline{w}$, and context variables $\overline{F}$ such that the set of true sentences of the form \[\forall r\;\exists\;\overline{F}\;\exists\;\overline{w}\;\; {\mathcal E}(p,r,\overline{F},\overline{w})\] is $\Pi_1^0$-hard (i.e., every co-r.e. set is many-one reducible to it), as $p$ ranges over finite words of a binary alphabet. Moreover, the existential prefix above contains just 5 context and 3 first-order variables. \end{abstract}

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121998
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 519674
Anderer: Local-ID: C1256104005ECAFC-55E49321AE36A06D412566FA003E613F-Vorobyov1998MFCS
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Brno, Czech Republic
Start-/Enddatum: 1998

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS-98)
Genre der Quelle: Konferenzband
 Urheber:
Brim, Lubos, Herausgeber
Gruska, Jozef, Herausgeber
Zlatuska, Jirí, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 597 - 606 Identifikator: ISBN: 3-540-64827-5

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1450 Artikelnummer: - Start- / Endseite: - Identifikator: -