Tractable and intractable second-order matching problems

DOI10.1016/J.JSC.2003.09.002MaRDI QIDQ2643530zbMATH OpenOpenAlexFDO

Authors Kouichi Hirata, Keizo Yamada, Masateru Harao

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)

Recommendations

• Publication:4938678
• Efficient second-order matching
• Matching - a special case of unification?
• scientific article; zbMATH DE number 1189058
• Decidable higher-order unification problems

Cites work

• scientific article; zbMATH DE number 4051039 (Why is no real title available?)
• scientific article; zbMATH DE number 1189058 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1223619 (Why is no real title available?)
• scientific article; zbMATH DE number 1302628 (Why is no real title available?)
• scientific article; zbMATH DE number 1341609 (Why is no real title available?)
• scientific article; zbMATH DE number 1104445 (Why is no real title available?)
• scientific article; zbMATH DE number 1552515 (Why is no real title available?)
• A Logic Programming Language with Lambda-Abstraction, Function Variables, and Simple Unification
• A unification algorithm for second-order monadic terms
• A unification algorithm for typed -calculus
• Decidable higher-order unification problems
• Efficient second-order matching
• Higher-order unification revisited: Complete sets of transformations
• Linear second-order unification
• On the undecidability of second-order unification
• Proving and applying program transformations expressed with second-order patterns
• Semantic generalizations for proving and disproving conjectures by analogy
• Simple second-order languages for which unification is undecidable
• The undecidability of the second order predicate unification problem
• The undecidability of the second-order unification problem

Cited in

(2)

• Efficient second-order matching
• scientific article; zbMATH DE number 1405696 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643530)