Dualizability of automatic algebras. (Q2436718): Difference between revisions

A partial automaton with state set \(Q\) and alphabet \(\Sigma\) is encoded as an algebra with one binary multiplication defined on the set \(Q\cup\Sigma\cup\{0\}\) by \(q\cdot a=r\) iff \(q@>a>>r\), for all \(q,r\in Q\) and \(a\in\Sigma\), and \(0\) for all other products. Automatic algebras have been studied mostly as a source of finite algebras with non-finitely based equational theories. See \textit{K. Kearnes} and \textit{R. Willard} [Can. Math. Bull. 37, No. 4, 514-521 (1994; Zbl 0815.08002)]; \textit{R. McKenzie} [Int. J. Algebra Comput. 6, No. 1, 49-104 (1996; Zbl 0844.08011)]; \textit{Z. Székely} [``Complexity of the finite algebra membership problem for varieties'', PhD thesis, University of South Carolina (1998)]; \textit{J. F. Boozer}, IV [``On finite axiomatizability of equational theories of automatic algebras'', PhD thesis, University of South Carolina (2010)]; \textit{G. F. McNulty} et al. [Int. J. Algebra Comput. 18, No. 8, 1283-1319 (2008; Zbl 1163.08002)]. Existing examples suggest that it may be a link between dualizability and finite basedness of finite automatic algebras. The paper starts a work on the George McNulty problem: ``Which finite automatic algebras are dualizable?'' (A dozen easy problems, Am. Math. Soc. Special Session, St. Paul, April 2010). The paper provides general characterization of dualizability of finite automatic algebras in two restricted classes, one with \(|\Sigma|=1\), and the other with \(|Q|=2\). The authors also give some necessary and some sufficient conditions for dualizability. In particular, they prove that a finite automatic algebra is dualizable if its letters act as an abelian group of permutations on its states. Moreover, the authors exhibit an infinite ascending chain \(A_1\leq A_2\leq A_3\leq\cdots\) of finite automatic algebras that are alternately dualizable and non-dualizable.