Pointlike sets for varieties determined by groups

DOI10.1016/J.AIM.2019.03.020MaRDI QIDQ2631933zbMATH OpenOpenAlexFDO

Authors Samuel J. van Gool, Benjamin Steinberg

Publication date 16 May 2019

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

semigroupsvarietiesseparation problempointlikes

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: For a variety of finite groups $mathbfH$, let $overlinemathbfH$ denote the variety of finite semigroups all of whose subgroups lie in $mathbfH$. We give a characterization of the subsets of a finite semigroup that are pointlike with respect to $overlinemathbfH$. Our characterization is effective whenever $mathbfH$ has a decidable membership problem. In particular, the separation problem for $overlinemathbfH$-languages is decidable for any decidable variety of finite groups $mathbfH$. This generalizes Henckell's theorem on decidability of aperiodic pointlikes.

Recommendations

• APERIODIC POINTLIKES AND BEYOND
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• IDEMPOTENT POINTLIKE SETS
• A delay theorem for pointlikes
• Some algorithmic problems for pseudovarieties

Cites work

• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 459360 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• A CHARACTERIZATION OF FINITE SOLUBLE GROUPS BY LAWS IN TWO VARIABLES
• A profinite approach to stable pairs.
• APERIODIC POINTLIKES AND BEYOND
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• An effective lower bound for group complexity of finite semigroups and automata
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Automata, dynamical systems, and groups
• Categories as algebra: An essential ingredient in the theory of monoids
• Complexity of finite semigroups
• Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands
• Finite semigroup varieties of the form V*D
• IDEMPOTENT POINTLIKE SETS
• INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY
• INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
• Identities for finite solvable groups and equations in finite simple groups
• Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
• On Pointlike Sets and Joins of Pseudovarieties
• On algorithmic problems for joins of pseudovarieties
• On the Decidability of Iterated Semidirect Products with Applications to Complexity
• On the extension problem for partial permutations
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• PROFINITE IDENTITIES FOR FINITE SEMIGROUPS WHOSE SUBGROUPS BELONG TO A GIVEN PSEUDOVARIETY
• PSEUDOVARIETY JOINS INVOLVING ${\mathscr J}$ -TRIVIAL SEMIGROUPS
• Pointlike sets with respect to R and J.
• Pointlike sets: the finest aperiodic cover of a finite semigroup
• Reducibility of pointlike problems
• Separating regular languages with first-order logic
• Solving systems of equations modulo pseudovarieties of Abelian groups and hyperdecidability.
• Some algorithmic problems for pseudovarieties
• The \(\mathfrak q\)-theory of finite semigroups.
• The pseudovariety $J$ is hyperdecidable
• The pseudovariety of all nilpotent groups is tame
• Yet another proof of the cascade decomposition theorem for finite automata

Cited in

(9)

• Pointlike sets and separation: a personal perspective
• On fixed point sets of distinguished collections for groups of parabolic characteristic.
• Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
• Product expansions
• Varieties
• First-order separation over countable ordinals
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• Constructing divisions into power groups
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS

This page was built for publication: Pointlike sets for varieties determined by groups

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