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$$.

MSC:
 68Q45 Formal languages and automata