zbMATH — the first resource for mathematics

On non-counting regular classes. (English) Zbl 0765.68074
Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 74-87 (1990).
[For the entire collection see Zbl 0758.00017.]
The main result of this paper is the following theorem: Let \(n\geq 5\). For any \(r\in M=A^*/\theta\) the Rees quotient \(N_ r=F_ r\cup\{0\}\) is finite. Therefrom one derives a positive solution of the “regularity of non-counting classes” — conjecture for \(n\geq 5\). More precisely one has:
Let \(n\) be a fixed integer \(\geq 5\). For any \(w\in A^*\) the congruence class \([w]_ n\) is a regular language.
The proof has been obtained both by algebraic and by combinatorical techniques. However, the cases \(n=2\) and \(n=3\) cannot be dealt with by our combinatorial tools. We believe, and we have strong evidence for this, that a slight refinement of our techniques will enable us to give a positive answer to the conjecture in the case \(n=4\).

68Q45 Formal languages and automata