Decidability of behavioural equivalence in unary PCF

✍ Scribed by Manfred Schmidt-Schauß

• Book ID: 104326467
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 750 KB
• Volume: 216
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00024-3

✦ Synopsis

Unary PCF is a fragment of the simply typed lambda-calculus PCF. We present a short proof that behavioral equivalence in unary PCF is decidable. An algorithm is described that enumerates all behaviorally equivalent expressions by increasing types, where types are ordered by a nested multiset ordering.