Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top