Word problem of the Perkins semigroup via directed acyclic graphs.
DOI10.1007/S11083-008-9083-7zbMATH Open1172.20040OpenAlexW2092388212MaRDI QIDQ953264FDOQ953264
Authors: Sergey Kitaev, Steve Seif 
Publication date: 17 November 2008
Published in: Order (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11083-008-9083-7
Recommendations
- Semiring identities of the Brandt monoid
- Monoids with sub-log-exponential free spectra.
- COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
- scientific article; zbMATH DE number 540502
- Small overlap monoids. I: The word problem.
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
- The word problem for semigroups presented by a single relation \(\langle A;\;a=bua\rangle\).
- The subword reversing method.
- Clones determined by alternating monoids
- Presentations of inverse monoids
Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18)
Cites Work
- The equivalence problem for finite rings
- Bases for equational theories of semi-groups
- On representable graphs
- Congruence modular varieties with small free spectra
- Monoids with sub-log-exponential free spectra.
- Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
- Results on the equivalence problem for finite groups.
- The complexity of checking identities for finite matrix rings
- The complexity of the word-problem for finite matrix rings
- COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
- The complexity of the equivalence problem for nonsolvable groups
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
- Free Objects in Certain Varieties of Inverse Semigroups
- Free Combinatorial Strict Inverse Semigroups
- Checking quasi-identities in a finite semigroup may be computationally hard.
- SOME INDECOMPOSABLE VARIETIES OF GROUPS
- Asymptotic growth of free spectra of band monoids.
Cited In (27)
- Monoids with sub-log-exponential free spectra.
- Word-representability of Toeplitz graphs
- On the representation number of a crown graph
- Minimum length word-representants of graph products
- Word-representability of graphs with respect to split recomposition
- Some results on Parikh word representable graphs and partitions
- Word-representability of triangulations of grid-covered cylinder graphs
- New results on word-representable graphs
- Word-representability of face subdivisions of triangular grid graphs
- Minimum length word-representants of word-representable graphs
- On operations preserving semi-transitive orientability of graphs
- Enumeration and extensions of word-representants
- Word-Representable Graphs: a Survey
- Word-representable graphs from a word's perspective
- Word-representable graphs: orientations, posets, and bounds
- Semi-transitive orientations and word-representable graphs
- Structural properties of word representable graphs
- Computing shortest 12-representants of labeled graphs
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- Representing graphs via pattern avoiding words
- Alternation graphs
- On semi-transitive orientability of Kneser graphs and their complements
- Properties of graphs specified by a regular language
- On word-representable and multi-word-representable graphs
- The complexity of the equivalence and equation solvability problems over meta-abelian groups
- On free spectra of a class of finite inverse monoids.
- Solving computational problems in the theory of word-representable graphs
This page was built for publication: Word problem of the Perkins semigroup via directed acyclic graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q953264)
