Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Solvability of Context Equations with Two Context Variables Is Decidable

Manfred Schmidt-SchaußContact Information and Klaus U. SchulzContact Information

(2)  Fachbereich Informatik, J.-W.-Goethe-Universität, Postfach 11 19 32, D-60054 Frankfurt, Germany
(3)  CIS, University of Munich, Oettingenstr 67, D-80538 München, Germany
Abstract
Context unification is a natural variant of second order unification that represents a generalization of word unification at the same time. While second order unification is wellknown to be undecidable and word unification is decidable it is currently open if solvability of context equations is decidable. We show that solvability of systems of context equations with two context variables is decidable. The context variables may have an arbitrary number of occurrences, and the equations may contain an arbitrary number of individual variables as well. The result holds under the assumption that the first-order background signature is finite

Contact Information Manfred Schmidt-Schauß
Email: schauss@ki.informatik.uni-frankfurt.de

Contact Information Klaus U. Schulz
Email: schulz@cis.uni-muenchen.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.108 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)