The equational complexity of Lyndon's algebra (Q539978)

For a variety \(\mathcal V\) of algebras, a function \(\beta_{\mathcal V}\) from the natural numbers into itself is the equational complexity of \(\mathcal V\) if a finite algebra \(B\) of the same type as \(\mathcal V\) of size \(\leq n\) belongs to \( \mathcal V\) just when \(B\) satisfies all identities of \(\mathcal V\) of length at most \( \beta_{\mathcal V}(n)\). We say that a variety \(\mathcal V\) is inherently nonfinitely based relative to a variety \(\mathcal W\) if no variety \(\mathcal U\) with \(\mathcal V \subseteq \mathcal U\subseteq \mathcal W\) is finitely based. This paper investigates varieties generated by automatic algebras (a groupoid \((A,\cdot )\) is an automatic algebra if there exists an automaton \((X,Q,\delta )\) -- assume that \(X\cap Q =\emptyset\) -- such that \(A=X\cup Q\cup \{0\}\) -- \(0\notin X\cup Q\) -- and \(q\cdot x=\delta (q,x)\) if \(q\in Q\) and \(x\in X\), and \(q\cdot x=0\) otherwise). The authors pay special attention to the seven-element Lyndon automatic algebra \(L\). Let \(\mathcal L\) be the variety generated by \(L\). The authors give a new proof for the fact that \(L\) is not finitely based. As consequences of the new proof they obtain that \(n-4\leq\beta_{\mathcal L}(n)\leq 2n+1\) for \(n\geq 4\) and that \(\mathcal L\) is inherently nonfinitely based relative to the variety generated by all automatic algebras. It is proved that for every finite \(m\neq 0,1, 4\) there exists a subdirectly irreducible algebra of size \(m\) belonging to \(\mathcal L\). A sufficient condition for a variety \(\mathcal V\) of algebras is stated so that the membership problem of \(\mathcal V\) is solvable in \(\log\)-space. Hence, the membership problem of every variety that is finitely based relative to the variety generated by all automatic algebras is solvable in \(\log\)-space (and is thus solvable in polynomial time).