Rewrite, rewrite, rewrite, rewrite, rewrite, \dots (Q1176247): Difference between revisions

Transfinite derivations having a limit and (infinitary) \(\alpha\)-normal forms (\(\alpha\) is an ordinal number) in term-rewriting systems are introduced. The following properties are particularly studied: \(\omega\)- closure, top-termination, \(\omega\)-normalization, \(\omega\)-confluence (sufficient and necessary conditions are derived). The usual connections between term-rewriting and (one-sorted) algebraic semantics are established. Sufficient completeness of hierarchical systems using constructors for the many-sorted case is also pointed out. The proofs are not omitted and clarifying examples are provided.