Pointlike sets for varieties determined by groups

DOI10.1016/J.AIM.2019.03.020zbMATH Open1453.20077arXiv1801.04638OpenAlexW2964318531MaRDI QIDQ2631933FDOQ2631933

Benjamin Steinberg, Samuel J. van Gool

Publication date: 16 May 2019

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

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.

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

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

zbMATH Keywords

semigroupsvarietiesseparation problempointlikes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Pointlike sets and separation: a personal perspective
• On fixed point sets of distinguished collections for groups of parabolic characteristic.
• Product expansions
• Varieties
• First-order separation over countable ordinals
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes
• 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)