Dualizability of automatic algebras.

DOI10.1016/J.JPAA.2013.11.020MaRDI QIDQ2436718zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 26 February 2014

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1475

zbMATH Keywords

dualizabilitydualizable algebrasfinite automatic algebrasnon-dualizable algebrasnon-finitely based equational theoriespartial automata

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05) Quasivarieties (08C15) Natural dualities for classes of algebras (08C20) Algebraic theory of languages and automata (68Q70)

Abstract: We make a start on one of George McNulty's Dozen Easy Problems: "Which finite automatic algebras are dualizable?" We give some necessary and some sufficient conditions for dualizability. For example, we prove that a finite automatic algebra is dualizable if its letters act as an abelian group of permutations on its states. To illustrate the potential difficulty of the general problem, we exhibit an infinite ascending chain $mathbf{A}_{1}lemathbf{A}_{2}lemathbf{A}_{3}le\mathrm{...}b$ of finite automatic algebras that are alternately dualizable and non-dualizable.

Review text

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.

Recommendations

• The equational complexity of Lyndon's algebra
• Tarski’s finite basis problem via 𝐀(𝒯)
• A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots).
• Automata in algebra
• Undecidability and finite automata
• Finiteness of the set of automaton Post bases with solvable completeness problem
• On the completeness of systems of finite automata
• Decision Problems for Finite Automata over Infinite Algebraic Structures
• On the classification of Post automaton bases according to the decidability of the completeness and \(A\)-completeness problems
• Algebras from finite group actions and a question of Eilenberg and Schützenberger

Cites work

• A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots).
• Binary homomorphisms and natural dualities
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Dualisability versus residual character: a theorem and a counterexample
• Dualisability. Unary algebras and beyond
• Dualizability and graph algebras
• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• Full duality among graph algebras and flat graph algebras
• scientific article; zbMATH DE number 3843821 (Why is no real title available?)
• scientific article; zbMATH DE number 1226180 (Why is no real title available?)
• Identities in Finite Algebras
• Inherent dualisability
• Inherently Nonfinitely Based Solvable Algebras
• Natural dualities for quasivarieties generated by a finite commutative ring.
• Natural dualities, nilpotence and projective planes
• Natural duality via a finite set of relations
• Near unanimity: An obstacle to general duality theory
• Nilpotent groups are not dualizable
• Some remarks on dualisability and endodualisability
• Strong duality for metacyclic groups
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• The Complexity of Dualisability: Three-Element Unary Algebras
• The dualisability of a quasi-variety is independent of the generating algebra.
• THE RESIDUAL BOUNDS OF FINITE ALGEBRAS
• Uncountably many dualisable algebras

Cited in

(6)

• Dualizability and graph algebras
• Sequential Automatic Algebras
• General algebra and its applications 2013: problem session.
• A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots).
• Natural dualities, nilpotence and projective planes
• Gödel algebras: interactive dualities and their applications.

This page was built for publication: Dualizability of automatic algebras.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436718)