Subalgebras of FA-presentable algebras.

DOI10.1007/S00012-014-0293-0zbMATH Open1321.08001arXiv1206.5548OpenAlexW2009230039MaRDI QIDQ466920FDOQ466920

Alan J. Cain, N. Ruškuc

Publication date: 31 October 2014

Published in: Algebra Universalis (Search for Journal in Brave)

Abstract: Automatic presentations, also called FA-presentations, were introduced to extend finite model theory to infinite structures whilst retaining the solubility of fundamental decision problems. This paper studies FA-presentable algebras. First, an example is given to show that the class of finitely generated FA-presentable algebras is not closed under forming finitely generated subalgebras, even within the class of algebras with only unary operations. However, it is proven that a finitely generated subalgebra of an FA-presentable algebra with a single unary operation is itself FA-presentable. Furthermore, it is proven that the class of unary FA-presentable algebras is closed under forming finitely generated subalgebras, and that the membership problem for such subalgebras is decidable.

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

zbMATH Keywords

regular languagesdecision problemsautomatic presentationsFA-presentationsfinitely generated subalgebrasunary FA-representable algebras

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Theory of numerations, effectively presented structures (03D45) Subalgebras, congruence relations (08A30) Applications of universal algebra in computer science (08A70)

Cites Work

• Title not available (Why is that?)
• Automaticity of ordinals and of homogeneous graphs
• Automatic linear orders and trees
• Finite automata presentable Abelian groups
• Deciding the isomorphism problem in classes of unary automatic structures
• Automatic presentations for semigroups.
• Automatic structures
• UNARY FA-PRESENTABLE SEMIGROUPS
• Unary automatic graphs: an algorithmic perspective
• STACS 2005
• FA-presentable groups and rings

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Subalgebras of simple AF-algebras 👍 👎
• Subalgebras of closure algebras 👍 👎
• On finitely presented algebras. 👍 👎
• Subalgebra extensions of partial monounary algebras 👍 👎
• SUBALGEBRAS OF DOUBLE FROBENIUS ALGEBRAS 👍 👎
• Subalgebras of free algebras 👍 👎
• Faithfulf-Free Algebras 👍 👎

This page was built for publication: Subalgebras of FA-presentable algebras.

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