patternMinor
The equational theory of regular languages has no finite set of axioms for general alphabets
Viewed 0 times
thefinitetheorylanguagesregularequationalgeneralhasforaxioms
Problem
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.
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.
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#91549, answer score: 4
Revisions (0)
No revisions yet.