Monadic recursion schemes: The effect of constants

摘要

When the class of monadic recursion schemes is augmented by individual constants, some of the properties change. It becomes undecidable whether “S diverges” or “S is strongly equivalent to T” for S, T schemes with individual constants. The family of value languages generated by this class of schemes is the family of recursively enumerable languages. The subclass of free schemes with constants is also investigated. It remains decidable whether “S halts” or “S diverges” for S a free scheme with individual constants, but it becomes undecidable whether “T has a strongly equivalent free scheme” for T an arbitrary scheme with individual constants.