HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can all regular tree types be expressed as $\mu$ types?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canallexpressedregulartypestree

Problem

In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct subtrees.

I'm wondering, is the converse true? Can every regular tree type be expressed using the $\mu$ fixpoint notation? It seems obvious that this can be done if you have mutually recursive types: you have a type for each subtree of the regular tree type. But can it be done with singly recursive types?

Solution

You can reduce mutual recursion to a single recursion, see Bekic's Theorem, see e.g. Section 10.1 of Winskel's (1), where Bekic is worked out for programs rather than types. Note however that the details depend on the exact nature of the formal system in question. See A. Bauer's answer in (2) for the case of types.

-
G. Winskel, The Formal Semantics of Programming Languages.

-
CSTheory Stackexchange, Can Isorecursive types capture mutually recursive data types?

Context

StackExchange Computer Science Q#109714, answer score: 7

Revisions (0)

No revisions yet.