Tractable and intractable second-order matching problems

DOI10.1016/j.jsc.2003.09.002zbMath1137.68411OpenAlexW2038779261MaRDI QIDQ2643530

Masateru Harao, Kouichi Hirata, Keizo Yamada

Publication date: 24 August 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2003.09.002

zbMATH Keywords

computational complexitysecond-order matching problemsecond-order unification problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple second-order languages for which unification is undecidable
• A unification algorithm for second-order monadic terms
• The undecidability of the second-order unification problem
• A unification algorithm for typed \(\overline\lambda\)-calculus
• Proving and applying program transformations expressed with second-order patterns
• Semantic generalizations for proving and disproving conjectures by analogy
• Higher-order unification revisited: Complete sets of transformations
• On the undecidability of second-order unification
• The undecidability of the second order predicate unification problem
• A Logic Programming Language with Lambda-Abstraction, Function Variables, and Simple Unification
• Efficient second-order matching
• Linear second-order unification
• Decidable higher-order unification problems

This page was built for publication: Tractable and intractable second-order matching problems