Dualizability of automatic algebras.

DOI10.1016/J.JPAA.2013.11.020zbMATH Open1306.08007arXiv1210.1475OpenAlexW1969394284MaRDI QIDQ2436718FDOQ2436718

Authors: Yanyan Li 

Publication date: 26 February 2014

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• Sequential Automatic Algebras
• Natural dualities, nilpotence and projective planes
• Dualizability and graph algebras
• 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.

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)