Reducibility of pointlike problems

DOI10.1007/S00233-015-9769-2MaRDI QIDQ2362748zbMATH OpenOpenAlexFDO

Authors Jorge Almeida, José Carlos Costa, Marc Zeitoun

Publication date 14 July 2017

Published in Semigroup Forum (Search for Journal in Brave)

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

zbMATH Keywords

aperiodic semigrouppointlike setprofinite semigrouppseudovarietyregular language

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07)

Abstract: We show that the pointlike and the idempotent pointlike problems are reducible with respect to natural signatures in the following cases: the pseudovariety of all finite semigroups in which the order of every subgroup is a product of elements of a fixed set of primes; the pseudovariety of all finite semigroups in which every regular J-class is the product of a rectangular band by a group from a fixed pseudovariety of groups that is reducible for the pointlike problem, respectively graph reducible. Allowing only trivial groups, we obtain omega-reducibility of the pointlike and idempotent pointlike problems, respectively for the pseudovarieties of all finite aperiodic semigroups (A) and of all finite semigroups in which all regular elements are idempotents (DA).

Recommendations

• Pointlike reducibility of pseudovarieties of the form V* D.
• Pointlike sets with respect to R and J.
• Reducibility vs. definability for pseudovarieties of semigroups
• IDEMPOTENT POINTLIKE SETS
• Complete reducibility of pseudovarieties.

Cites work

• A profinite approach to stable pairs.
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• APERIODIC POINTLIKES AND BEYOND
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• Complete reducibility of systems of equations with respect to \(\mathbf R\).
• Dynamics of implicit operations and tameness of pseudovarieties of groups
• scientific article; zbMATH DE number 988806 (Why is no real title available?)
• scientific article; zbMATH DE number 459360 (Why is no real title available?)
• scientific article; zbMATH DE number 1419247 (Why is no real title available?)
• 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
• On some systems of equations with constraints in a free group. -- Addenda.
• On the Decidability of Iterated Semidirect Products with Applications to Complexity
• Pointlike sets with respect to R and J.
• Pointlike sets: the finest aperiodic cover of a finite semigroup
• Representations of the free profinite object over \(\mathbf{DA}\).
• Separating regular languages by piecewise testable and unambiguous languages
• Separating regular languages with first-order logic
• Some algorithmic problems for pseudovarieties
• Tameness of pseudovariety joins involving R.
• The \(\mathfrak q\)-theory of finite semigroups.
• The word problem for \(\omega \)-terms over DA

Cited in

(6)

• Towards a pseudoequational proof theory
• Pointlike sets for varieties determined by groups
• Pointlike reducibility of pseudovarieties of the form V* D.
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• Some reducibility properties for pseudovarieties of the form DRH
• Pseudovarieties of semigroups

This page was built for publication: Reducibility of pointlike problems

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