INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES

DOI10.1142/S0218196791000079zbMATH Open0722.20039OpenAlexW2046268252WikidataQ123258428 ScholiaQ123258428MaRDI QIDQ3209328FDOQ3209328

Authors: C. J. Ash 

Publication date: 1991

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196791000079

Recommendations

• A NEW PROOF OF THE RHODES TYPE II CONJECTURE
• Type-II conjecture is true for finite \(\mathcal J\)-trivial monoids
• Graph products of monoids
• Reduction theorem for the type-II conjecture for finite monoids
• SC-hyperdecidability of \(\mathbf R\)

zbMATH Keywords

factorizationsfinite monoidsfinite directed graphsrelational morphismsinevitable graphsType II Conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Algebraic theory of languages and automata (68Q70) Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (only showing first 100 items - show all)

• Iterated periodicity over finite aperiodic semigroups
• Extending partial automorphisms and the profinite topology on free groups
• Graph expansions of unipotent monoids
• UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS
• On the equation \({\mathbf V}*{\mathbf G}={\mathcal E}{\mathbf V}\)
• Covers for monoids.
• PROFINITE METHODS IN SEMIGROUP THEORY
• Pointlike sets and separation: a personal perspective
• ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS
• Towards a pseudoequational proof theory
• Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
• The geometry of profinite graphs with applications to free groups and finite monoids
• MODULES
• On \(\kappa\)-reducibility of pseudovarieties of the form \(V \ast D\)
• Algebras of right ample semigroups
• A unified syntactical approach to theorems of Putcha, Margolis, and Straubing on finite power semigroups
• Every decidable pseudovariety of abelian groups is completely tame
• INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY
• POLYNOMIAL CLOSURE AND TOPOLOGY
• APERIODIC POINTLIKES AND BEYOND
• Polynomial closure of group languages and open sets of the Hall topology
• On a locality-like property of the pseudovariety J
• A profinite approach to stable pairs.
• COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
• Reducibility of pointlike problems
• On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
• COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
• Tameness of joins involving the pseudovariety of local semilattices.
• TAMENESS OF THE PSEUDOVARIETY LS1
• Abelian kernels, profinite topologies and the extension problem
• An upper bound for the power pseudovariety \(\mathbf{PCS}\).
• Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
• The \(\mathbf G\)-exponent of a pseudovariety of semigroups
• Reducibility vs. definability for pseudovarieties of semigroups
• Monoid kernels and profinite topologies on the free Abelian group
• Pointlike reducibility of pseudovarieties of the form \(\mathbf V*\mathbf D\).
• A syntactic approach to covers for E ‐dense semigroups over group varieties
• The finite basis problem in the pseudovariety joins of aperiodic semigroups with groups
• Inverse automata and profinite topologies on a free group
• The pseudoidentity problem and reducibility for completely regular semigroups
• A NEW PROOF OF THE RHODES TYPE II CONJECTURE
• On Pointlike Sets and Joins of Pseudovarieties
• CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATA
• Completely regular semigroup varieties generated by Mal'cev products with groups
• Dynamics of implicit operations and tameness of pseudovarieties of groups
• Finite loops recognize exactly the regular open languages
• SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS
• Polynomial closure of group languages and open sets of the Hall topology
• Pointlike sets with respect to R and J.
• An application of a theorem of Ash to finite covers.
• Relative Abelian kernels of some classes of transformation monoids
• Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
• On discrete hyperbolic arboreal groups
• Pointlike sets for varieties determined by groups
• A constructive version of the Ribes-Zalesskiĭ product theorem.
• CATEGORIES AS ALGEBRA, II
• On \(F\)-inverse covers of finite-above inverse monoids.
• Closures of regular languages for profinite topologies.
• Polynomial closure and unambiguous product
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
• PSEUDOVARIETY JOINS INVOLVING ${\mathscr J}$ -TRIVIAL SEMIGROUPS
• COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• PROFINITE SEMIGROUPS, VARIETIES, EXPANSIONS AND THE STRUCTURE OF RELATIVELY FREE PROFINITE SEMIGROUPS
• The pseudovariety $J$ is hyperdecidable
• New results on the conjecture of Rhodes and on the topological conjecture
• Constructing divisions into power groups
• Profinite topologies
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• Finite state automata: a geometric approach
• SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
• IDEMPOTENT POINTLIKE SETS
• TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS
• On \(F\)-inverse covers of inverse monoids.
• Semidirect product with an order-computable pseudovariety and tameness.
• Computing relative Abelian kernels of finite monoids.
• SC-hyperdecidability of \(\mathbf R\)
• Tameness of pseudovariety joins involving R.
• Krohn-Rhodes complexity of Brauer type semigroups.
• All about unambiguous polynomial closure
• Finitely approximable groups and actions. I: The Ribes-Zalesskiĭ property
• John Rhodes and the theory of finite semigroups.
• On the hyperdecidability of semidirect products of pseudovarieties
• Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples
• ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS
• On non-commuting sets in finite soluble CC-groups.
• About the power pseudovariety \(\mathbf{PCS}\)
• On All Things Star-Free
• On the power pseudovariety \(\mathbf{PCS}\).
• The pseudovariety of all nilpotent groups is tame
• Some reducibility properties for pseudovarieties of the form \(DRH\)
• First-order separation over countable ordinals
• Krohn-Rhodes complexity pseudovarieties are not finitely based
• On Radical Congruence Systems II
• WHAT ARE MODULES? AN OVERVIEW OF BRET TILSON'S PAPER "MODULES" FROM A GEOMETRIC VIEWPOINT
• Commutative images of rational languages and the Abelian kernel of a monoid
• An effective lower bound for group complexity of finite semigroups and automata
• Conelikes and ranker comparisons
• STABLE PAIRS
• Characterizing level one in group-based concatenation hierarchies

This page was built for publication: INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES

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