← All problems
Unverified

Has any full, finitely-generated and Church-Rosser term-rewriting system (or system with bound variables) a recursive, one-step, normalizing reduction strategy?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

Let a term-rewriting system (or more generally, a system with bound variables [Kennaway, 1991]) have the following properties: it is finitely generated'' (has finitely many function symbols and rules), it is full'' (its terms are all that can be formed from the function symbols), and it is Church-Rosser. Does it follow that it has a recursive, one-step, normalizing reduction strategy? (There are counterexamples if any of the three conditions is dropped.) Kennaway [Kennaway, 1991] showed that for ``weakly'' orthogonal systems the answer is yes. So, any counterexample must come from the murky world of non-orthogonal systems. See also [Kennaway, 1991].

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu