Complexity of the higher order matching

DOI10.1007/3-540-48660-7_6MaRDI QIDQ4263158zbMATH OpenFDO

Authors Tomasz Wierzbicki

Publication date 22 September 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48660-7_6

zbMATH Keywords

complexitydecidabilityfourth-order matchinghigher-order matchingNP-hardness boundssatisfiabilitysimply typed lambda calculus

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Combinatory logic and lambda calculus (03B40) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Linear higher-order matching is NP-complete
• scientific article; zbMATH DE number 2043532
• Term Rewriting and Applications
• Decidability of fourth-order matching
• Higher-order matching and tree automata

Cited in

(11)

• Deterministic second-order patterns
• Complexity of matching problems
• Decidability of bounded higher-order unification
• Tractable and intractable second-order matching problems
• Linear higher-order matching is NP-complete
• The role of polymorphism in the characterisation of complexity by soft types
• Higher order matching polynomial
• scientific article; zbMATH DE number 2043532 (Why is no real title available?)
• Term Rewriting and Applications
• Automated Deduction – CADE-19
• Computational complexity of simultaneous elementary matching problems

This page was built for publication: Complexity of the higher order matching

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