Word problem of the Perkins semigroup via directed acyclic graphs.
From MaRDI portal
Publication:953264
DOI10.1007/s11083-008-9083-7zbMath1172.20040OpenAlexW2092388212MaRDI QIDQ953264
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
Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Inverse semigroups (20M18)
Related Items (22)
Structural properties of word representable graphs ⋮ Word-representability of triangulations of grid-covered cylinder graphs ⋮ Word-Representable Graphs: a Survey ⋮ Word-representability of face subdivisions of triangular grid graphs ⋮ New results on word-representable graphs ⋮ On semi-transitive orientability of Kneser graphs and their complements ⋮ On word-representable and multi-word-representable graphs ⋮ The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group ⋮ Some results on Parikh word representable graphs and partitions ⋮ On operations preserving semi-transitive orientability of graphs ⋮ Minimum length word-representants of word-representable graphs ⋮ Semi-transitive orientations and word-representable graphs ⋮ Solving computational problems in the theory of word-representable graphs ⋮ Representing graphs via pattern avoiding words ⋮ Enumeration and extensions of word-representants ⋮ On the representation number of a crown graph ⋮ Monoids with sub-log-exponential free spectra. ⋮ Properties of graphs specified by a regular language ⋮ Alternation Graphs ⋮ ON FREE SPECTRA OF A CLASS OF FINITE INVERSE MONOIDS ⋮ Word-representability of Toeplitz graphs ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups
Cites Work
- Checking quasi-identities in a finite semigroup may be computationally hard.
- The equivalence problem for finite rings
- Asymptotic growth of free spectra of band monoids.
- Monoids with sub-log-exponential free spectra.
- Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
- Bases for equational theories of semi-groups
- Results on the equivalence problem for finite groups.
- The complexity of checking identities for finite matrix rings
- Free Objects in Certain Varieties of Inverse Semigroups
- Free Combinatorial Strict Inverse Semigroups
- 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
- On representable graphs
- SOME INDECOMPOSABLE VARIETIES OF GROUPS
- Congruence modular varieties with small free spectra
This page was built for publication: Word problem of the Perkins semigroup via directed acyclic graphs.
