The undecidability of pattern matching in calculi where primitive recursive functions are representable

DOI10.1016/0304-3975(93)90175-SzbMATH Open0773.03011OpenAlexW2072809974MaRDI QIDQ1208421FDOQ1208421

Authors: Gilles Dowek 

Publication date: 16 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90175-s

Recommendations

• scientific article; zbMATH DE number 29189
• scientific article; zbMATH DE number 445160
• Higher Order   Matching is Undecidable
• scientific article; zbMATH DE number 2186938
• scientific article; zbMATH DE number 2182490

zbMATH Keywords

pattern matchingprimitive recursive functionsHilbert's tenth problemGirard's system \(F\)calculi supporting inductive typespolymorphic \(\lambda\)-calculiGödel's system \(T\)

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Combinatory logic and lambda calculus (03B40) Recursive functions and relations, subrecursive hierarchies (03D20) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• Hilbert's Tenth Problem is Unsolvable
• Title not available (Why is that?)
• Introduction to generalized type systems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Third-order matching in the polymorphic lambda calculus
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: The undecidability of pattern matching in calculi where primitive recursive functions are representable

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