Pointlike sets: the finest aperiodic cover of a finite semigroup

DOI10.1016/0022-4049(88)90042-4zbMath0682.20044OpenAlexW1981565742MaRDI QIDQ1824040

Karsten Henckell

Publication date: 1988

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-4049(88)90042-4

zbMATH Keywords

complexityfinite semigroupsaperiodic semigroupsdecidableRhodes expansionsfinest coverPresentation LemmaZeiger coding

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Representation of semigroups; actions of semigroups on sets (20M30)

Related Items

ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS ⋮ INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY ⋮ PROFINITE METHODS IN SEMIGROUP THEORY ⋮ Reducibility of pointlike problems ⋮ Pointlike sets and separation: a personal perspective ⋮ Pointlike sets for varieties determined by groups ⋮ Product expansions ⋮ Subsemigroups and complexity via the presentation lemma ⋮ Some reducibility properties for pseudovarieties of the form DRH ⋮ McCammond’s normal forms for free aperiodic semigroups revisited ⋮ Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples ⋮ Living without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions ⋮ Conelikes and ranker comparisons ⋮ First-order separation over countable ordinals ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ John Rhodes and the theory of finite semigroups. ⋮ Closures of regular languages for profinite topologies. ⋮ An effective lower bound for group complexity of finite semigroups and automata ⋮ Towards a pseudoequational proof theory ⋮ Pointlike sets with respect to R and J. ⋮ STABLE PAIRS ⋮ A PROFINITE APPROACH TO STABLE PAIRS ⋮ APERIODIC POINTLIKES AND BEYOND ⋮ The pseudovariety $J$ is hyperdecidable ⋮ IDEMPOTENT POINTLIKE SETS ⋮ On Pointlike Sets and Joins of Pseudovarieties ⋮ Unnamed Item ⋮ On All Things Star-Free ⋮ Prime decomposition theorem for arbitrary semigroups: General holonomy decomposition and synthesis theorem ⋮ Varieties ⋮ Profinite topologies ⋮ Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes ⋮ On the hyperdecidability of semidirect products of pseudovarieties ⋮ PSEUDOVARIETY JOINS INVOLVING ${\mathscr J}$ -TRIVIAL SEMIGROUPS ⋮ HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS ⋮ POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS ⋮ UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS

Cites Work

• Unnamed Item
• On the complexity of finite semigroups
• Prime decomposition theorem for arbitrary semigroups: General holonomy decomposition and synthesis theorem
• Cascade synthesis of finite-state machines