Third order matching is decidable

Annals of Pure and Applied Logic 69 (2-3):135-155 (1994)
  Copy   BIBTEX


The higher order matching problem is the problem of determining whether a term is an instance of another in the simply typed [lgr]-calculus, i.e. to solve the equation a = b where a and b are simply typed [lgr]-terms and b is ground. The decidability of this problem is still open. We prove the decidability of the particular case in which the variables occuring in the problem are at most third order



    Upload a copy of this work     Papers currently archived: 91,252

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

An Undecidable Linear Order That Is $n$-Decidable for All $n$.John Chisholm & Michael Moses - 1998 - Notre Dame Journal of Formal Logic 39 (4):519-526.
Pure Second-Order Logic with Second-Order Identity.Alexander Paseau - 2010 - Notre Dame Journal of Formal Logic 51 (3):351-360.
Decidable discrete linear orders.M. Moses - 1988 - Journal of Symbolic Logic 53 (2):531-539.
Unification grammars and off-line parsability.Efrat Jaeger, Nissim Francez & Shuly Wintner - 2005 - Journal of Logic, Language and Information 14 (2):199-234.
Decidable subspaces and recursively enumerable subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
A decidable variety that is finitely undecidable.Joohee Jeong - 1999 - Journal of Symbolic Logic 64 (2):651-677.
An Event-Based Fragment of First-Order Logic over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
On first-order theories with provability operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
Decidable fragments of first-order modal logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
Automatic structures of bounded degree revisited.Dietrich Kuske & Markus Lohrey - 2011 - Journal of Symbolic Logic 76 (4):1352-1380.


Added to PP

6 (#1,397,076)

6 months
1 (#1,478,435)

Historical graph of downloads
How can I increase my downloads?