Automatic semigroups and categories.

DOI10.1016/J.TCS.2005.11.021MaRDI QIDQ2368995zbMATH OpenOpenAlexFDO

Authors Mark Kambites

Publication date 28 April 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.11.021

zbMATH Keywords

automatic semigroupsautomatic structuresfree categoriesgraphsregular languagessemigroupoidssmall categories

Mathematics Subject Classification ID

Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40) Groupoids (i.e. small categories in which all morphisms are isomorphisms) (20L05) Free semigroups, generators and relations, word problems (20M05) Connections of semigroups with homological algebra and category theory (20M50) Formal languages and automata (68Q45)

Review text

The author extends some theoretical results on automatic semigroups to automatic semigroupoids (and small categories). The basic combinatorial notions of generators and relations generalise via graphs and paths substituting for alphabets and words, respectively. The author introduces natural definitions of automaticity and prefix-automaticity in the framework of semigroupoids and explores their consequences. He shows that a semigroupoid is automatic or prefix-automatic if and only if some closely associated semigroup has the same property. As a consequence, he shows that the class of prefix-automatic semigroups is closed under the taking of cofinite subsemigroups, free products, and free factors.

Recommendations

• Automatic Rees matrix semigroups over categories.
• Quasi-automatic semigroups
• Notions of automaticity in semigroups.
• Automatic semigroups
• Automatic subsemigroups of free products.

Cites work

• A database of categories.
• A Geometric Characterization of Automatic Monoids
• A practical method for enumerating cosets of a finite abstract group
• Automatic completely-simple semigroups
• Automatic monoids and change of generators
• Automatic Rees matrix semigroups over categories.
• Automatic semigroups
• AUTOMATIC SEMIGROUPS WITH SUBSEMIGROUPS OF FINITE REES INDEX
• Automaticity and commutative semigroups
• Categories as algebra: An essential ingredient in the theory of monoids
• Computing left Kan extensions.
• Extensions and submonoids of automatic monoids.
• scientific article; zbMATH DE number 1604229 (Why is no real title available?)
• scientific article; zbMATH DE number 19482 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 1254101 (Why is no real title available?)
• scientific article; zbMATH DE number 1944128 (Why is no real title available?)
• scientific article; zbMATH DE number 1529076 (Why is no real title available?)
• scientific article; zbMATH DE number 1750601 (Why is no real title available?)
• scientific article; zbMATH DE number 784870 (Why is no real title available?)
• scientific article; zbMATH DE number 3284302 (Why is no real title available?)
• scientific article; zbMATH DE number 3358760 (Why is no real title available?)
• Notions of automaticity in semigroups.
• PRESENTATIONS FOR SEMIGROUPS AND SEMIGROUPOIDS
• The Todd-Coxeter procedure and left Kan extensions
• Using rewriting systems to compute left Kan extensions and induced actions of categories

Cited in

(5)

• A note on automatic semigroups.
• Automatic Rees matrix semigroups over categories.
• The loop problem for Rees matrix semigroups.
• Automatic semigroups vs automaton semigroups
• Relational semigroupoids: abstract relation-algebraic interfaces for finite relations between infinite types

This page was built for publication: Automatic semigroups and categories.

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