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

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

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.

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

• scientific article; zbMATH DE number 3843821 (Why is no real title available?)
• scientific article; zbMATH DE number 1226180 (Why is no real title available?)
• 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
• 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 RESIDUAL BOUNDS OF FINITE ALGEBRAS
• The Complexity of Dualisability: Three-Element Unary Algebras
• The dualisability of a quasi-variety is independent of the generating algebra.
• Uncountably many dualisable algebras

Cited in

(6)

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

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)