Word problem of the Perkins semigroup via directed acyclic graphs.

DOI10.1007/s11083-008-9083-7zbMath1172.20040MaRDI QIDQ953264

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

zbMATH Keywords

computational complexity; word problem; Brandt monoid; word graphs

Mathematics Subject Classification ID

20M05: Free semigroups, generators and relations, word problems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C20: Directed graphs (digraphs), tournaments

20M18: Inverse semigroups

Related Items

Word-Representable Graphs: a Survey, Enumeration and extensions of word-representants, Properties of graphs specified by a regular language, The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group, Word-representability of triangulations of grid-covered cylinder graphs, Word-representability of face subdivisions of triangular grid graphs, New results on word-representable graphs, Representing graphs via pattern avoiding words, Semi-transitive orientations and word-representable graphs, On the representation number of a crown graph, On semi-transitive orientability of Kneser graphs and their complements, Word-representability of Toeplitz graphs, The complexity of the equivalence and equation solvability problems over meta-abelian groups, Some results on Parikh word representable graphs and partitions, On operations preserving semi-transitive orientability of graphs, Monoids with sub-log-exponential free spectra., Structural properties of word representable graphs, ON FREE SPECTRA OF A CLASS OF FINITE INVERSE MONOIDS, Alternation Graphs, Solving computational problems in the theory of word-representable graphs

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