Linear Higher-Order Matching Is NP-Complete | Zendy

Philippe de Groote | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Linear Higher-Order Matching Is NP-Complete

Author(s) -

Philippe de Groote

Publication year - 2000

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-67778-X

DOI - 10.1007/10721975_9

Subject(s) - decidability , heuristics , computer science , matching (statistics) , time complexity , np complete , order (exchange) , set (abstract data type) , abstraction , algorithm , computational complexity theory , combinatorics , discrete mathematics , theoretical computer science , mathematics , programming language , philosophy , statistics , finance , epistemology , economics , operating system

We consider the problem of higher-order matching restricted to the set of linear -terms (i.e., -terms where each abstraction x.M is such that there is exactly one free occurrence of x in M). We prove that this problem is decidable by showing that it belongs to NP. Then we prove that this problem is in fact NP-complete. Finally, we discuss some heuristics for a practical algorithm.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research