On The Problem Of Generating Small Convergent Systems

✍ Scribed by Klaus Madlener; Andrea Sattler-Klein; Friedrch Otto

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 671 KB
• Volume: 16
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1993.1040

✦ Synopsis

A sequence (\left(R_{n, m}\right)_{n, m \in \mathbb{N}}) of normalized string-rewriting systems on a fixed finite alphabet (\Sigma) is constructed such that, for all (n, m \in \mathbb{N}),

1. (R_{n, m}) contains 44 rules, it is of size (O(n+m)), and it is compatible with a lengthlexicographical ordering (>) on (\Sigma^{*}), but

2. given the system (R_{n, m}) and the ordering (>) as input, the Knuth-Bendix completion procedure will generate more than (A(n, m)) intermediate rules before a finite convergent system (S_{n, m}) of size (O(n+m)) is obtained. Here (A) denotes Ackermann's function.