A delay theorem for pointlikes

DOI10.1007/S002330010051MaRDI QIDQ5952235zbMATH OpenOpenAlexFDO

Authors Benjamin Steinberg

Publication date 30 September 2003

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002330010051

zbMATH Keywords

decidable pointlikesfinite categoriesfinite semigroupsmonoid pseudovarietiespointlike setsprofinite categoriespseudovarieties of categoriessemidirect productssemigroup pseudovarieties

Mathematics Subject Classification ID

Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40) Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07) Connections of semigroups with homological algebra and category theory (20M50)

Review text

For a fixed pseudovariety \(\mathbb{V}\) of semigroups (or monoids), a subset \(P\) of a finite semigroup \(S\) is said to be \(\mathbb{V}\)-pointlike if \(P\) relates to a single element under every relational morphism between \(S\) and a semigroup (or a monoid) in \(\mathbb{V}\). One says that \(\mathbb{V}\) has decidable pointlikes if, given a finite semigroup \(S\) and a subset \(P\subseteq S\), one can decide whether or not \(P\) is \(\mathbb{V}\)-pointlike. Let \(\mathbb{D}\) denote the pseudovariety of all finite semigroups in which every idempotent is a right zero. The main result of the paper (Theorem 1.2) shows that a monoid pseudovariety \(\mathbb{V}\) has decidable pointlikes if and only if the semidirect product \(\mathbb{V}*\mathbb{D}\) has decidable pointlikes. This generalizes the so-called Delay Theorem by \textit{B.~Tilson} [J. Pure Appl. Algebra 48, 83-198 (1987; Zbl 0627.20031)]. In fact, the author gives a nice description of the \(\mathbb{V}*\mathbb{D}\)-pointlike sets of a given semigroup \(S\) in terms of the \(\mathbb{V}\)-pointlike sets of a certain category formed from the idempotents of \(S\). The main technical tool of the paper is the notion of a profinite category.

Recommendations

• Some algorithmic problems for pseudovarieties
• scientific article; zbMATH DE number 1972777
• scientific article; zbMATH DE number 4008680
• APERIODIC POINTLIKES AND BEYOND
• ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS
• Decidability and tameness in the theory of finite semigroups.
• scientific article; zbMATH DE number 1746555
• On a problem of Brzozowski and Fich
• PROFINITE METHODS IN SEMIGROUP THEORY
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS

Cited in

(12)

• Varieties
• Generic results for concatenation hierarchies
• Pointlike sets with respect to R and J.
• Pointlike sets for varieties determined by groups
• On the decidability of membership in the global of a monoid pseudovariety.
• A profinite approach to stable pairs.
• APERIODIC POINTLIKES AND BEYOND
• COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
• The geometry of profinite graphs with applications to free groups and finite monoids
• PROFINITE METHODS IN SEMIGROUP THEORY
• Covering and separation for logical fragments with modular predicates
• Pointlike sets and separation: a personal perspective

This page was built for publication: A delay theorem for pointlikes

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