MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Vorobyov, Sergeidblp
Editor(s):
Brim, Lubos
Gruska, Jozef
Zlatuska, Jirí		dblp
dblp
dblp
BibTeX cite key*:
Vorobyov1998MFCS
Title, Booktitle
Title*:
$\forall\exists^\ast$-Equational Theory of Context Unification is $\Pi_1^0$-Hard
Booktitle*:
Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS-98)
Event, URLs
Conference URL::
http://www.fi.muni.cz/mfcs98/
Downloading URL:
Event Address*:
Brno, Czech Republic
Language:
English
Event Date*
(no longer used):
August 1998
Organization:
Mazaryk University, European Assoc of Computer Science Logic
Event Start Date:
14 May 2024
Event End Date:
14 May 2024
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1450
Number:
Month:
August
Pages:
597-606
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-64827-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
\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}
Keywords:
Context unification, first-order theories, undecidability
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, CCL bibliography



BibTeX Entry:
@INPROCEEDINGS{Vorobyov1998MFCS,
AUTHOR = {Vorobyov, Sergei},
 EDITOR = {Brim, Lubos and Gruska, Jozef and Zlatuska, Jir{\'i}},
 TITLE = {$\forall\exists^\ast$-Equational Theory of Context Unification is ${\Pi}_1^0$-Hard},
 BOOKTITLE = {Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 ORGANIZATION = {Mazaryk University, European Assoc of Computer Science Logic},
 VOLUME = {1450},
 PAGES = {597--606},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Brno, Czech Republic},
 MONTH = {August},
 ISBN = {3-540-64827-5},
}

Entry last modified by Uwe Brahm, 03/12/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Sergei Vorobyov		Created
01/15/1999 12:21:21 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Sergei Vorobyov
Edit Dates
31.03.99 17:23:19
31.03.99 17:22:48
29.03.99 19:35:45
29.03.99 19:35:45