4
$\begingroup$

According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms.

Why does this imply that it has no finite set of axioms over an arbitrary alphabet?

Suppose I have a finite set of axioms for the equational theory of an alphabet with more than one letter, how would this give a finite set of axioms for the single letter case? I mean in the single letter case we have additional equations which did not hold in the arbitrary case, for examle $AB = BA$ for two languages $A,B$, and therefore which could not be derived from the axioms, hence these axioms do not axiomatize the single letter case.

Some clarification as asked for in the comments: Given a fixed alphabet $\Sigma$ and a set of variables $X = \{A,B,C,\ldots\}$, the terms are inductively defined:

1) Every $a \in \Sigma$ is a term,

2) Every variable $X$ is a term,

3) If $s,t$ are terms, then $s + t, s\cdot t, t^{\ast}$ are terms.

The interpretation of the regular sets $\mathcal{Reg}(\Sigma)\subseteq \mathcal P(\Sigma^{\ast})$ is as usual. As written in the comments, as set of terms $\Gamma$ axiomises $\mathcal{Reg}(\Sigma)$, the regular languages over a given alphabet $\Sigma$, if $$ \Gamma \vdash t_1 = t_2 \mbox{ iff } \mathcal{Reg}(\Sigma) \models t_1 = t_2. $$ Where $t_1, t_2$ are terms with alphabet letters from $\Sigma$, and variables are interpreted as universally quantified. The only rule of interference being substitution, that I mean by equational logic.

$\endgroup$
  • $\begingroup$ Is there a reference in English? $\endgroup$ – Leo163 May 6 '18 at 11:39
  • 1
    $\begingroup$ I had not read the russian article either, but I know the proofs in the unary alphabet case from A. Ginsburg, Algebraic Theory of Automata and J.H. Conway Regular Algebra and Machines. But they both do not give details for how the result for arbitrary alphabets is implied. $\endgroup$ – StefanH May 6 '18 at 11:45
  • $\begingroup$ Nice question! Two little facts: (1) $L + \{a\}^* = \{a\}^*$ is equivalent to saying that the language $L$ uses only the single letter $a$; (2) the conjunction $(t_1 = u_1) \land (t_2 = u_2)$ is equivalent to the equality $(a_1 t_1 + a_2 t_2) = (a_1 u_1 + a_2 u_2)$, where we expand the alphabet to add two new letters $a_1,a_2$ that aren't mentioned in $t_1,t_2,u_1,u_2$, so we can express conjunctions of equalities as a single equality (in the case of a multi-letter alphabet). I can't see how to use this to prove a reduction, though. $\endgroup$ – D.W. May 6 '18 at 20:48
  • $\begingroup$ @D.W. Today I had an idea to prove it, but it is based on the knowledge that we know a complete axiom system for unary languages. See me own answer. $\endgroup$ – StefanH May 7 '18 at 8:41
4
$\begingroup$

For each $k > 0$, the equation $$ A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}) $$ holds for regular languages over every alphabet, hence if for some alphabet we have a finite axiomatization, this equation is provable from it. Now as shown in A. Ginsburg, Algebraic Theory of Automata, the following infinite system of axioms is complete for unary regular languages. \begin{align*} A + B & = B + A \\ A + (B + C) & = (A + B) + C \\ A + A & = A \\ A + \emptyset & = A \\ AB &= BA \\ (AB)C & = A(BC) \\ A1 & = A \\ A \emptyset & = \emptyset \\ (A+B)C & = AC + BC \\ 1^{\ast} & = 1, \emptyset^{\ast} = 1 \\ (AB^{\ast})^{\ast} & = 1 + AA^{\ast}B^{\ast} \\ (A + B)^{\ast} & = A^{\ast} B^{\ast} \\ A^{\ast} & = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}), \quad k > 0 \end{align*} So we get a finite axiomatisation for unary languages, if we take but the last family of axioms, and all axioms from the finite axiom system for some alphabet that prove $$ A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}) $$ for each $k > 0$. Then all of the above equations are derivable by this finite axiom system, and as the above one is complete, this finite axiom system would be complete, which is not possible. Hence there is no finite system of axioms for any alphabet.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.