Conjugacy in monoids with a special Church-Rosser presentation is decidable
From MaRDI portal
Publication:801163
DOI10.1007/BF02573327zbMath0551.20044MaRDI QIDQ801163
Publication date: 1984
Published in: Semigroup Forum (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/134684
equivalence relationsword problemdecidabilityfree monoidsconjugacy problemfinitely presented monoidsChurch-Rosser Thue systemsconjugacy relations
Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Mappings of semigroups (20M15) Thue and Post systems, etc. (03D03)
Related Items
Finite derivation type for Rees matrix semigroups ⋮ The problems of cyclic equality and conjugacy for finite complete rewriting systems ⋮ Decidability and independence of conjugacy problems in finitely presented monoids ⋮ Thue systems as rewriting systems ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ A note on regular classes in special Thue systems ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems ⋮ Deciding conjugacy in sylvester monoids and other homogeneous monoids ⋮ Idempotent varieties of incidence monoids and bipartite posets ⋮ Unnamed Item ⋮ Normal subsemigroups of finite transformation semigroups ⋮ A new definition of conjugacy for semigroups ⋮ The Knuth-Bendix algorithm and the conjugacy problem in monoids. ⋮ The monoid of queue actions ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Unnamed Item ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ Conjugacy in special monoids ⋮ Unnamed Item ⋮ The word problem for one-relation monoids: a survey ⋮ Crystallizing the hypoplactic monoid: from quasi-Kashiwara operators to the Robinson-Schensted-Knuth-type correspondence for quasi-ribbon tableaux ⋮ Conjugacy in inverse semigroups ⋮ Conjugation in semigroups. ⋮ On three approaches to conjugacy in semigroups. ⋮ On equations and first-order theory of one-relator monoids ⋮ Semigroups presented by one relation and satisfying the Church-Rosser property ⋮ Combinatorics of cyclic shifts in plactic, hypoplactic, Sylvester, Baxter, and related monoids ⋮ On Finite Complete Presentations and Exact Decompositions of Semigroups ⋮ Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids ⋮ The transitivity of primary conjugacy in regular \(\omega\)-semigroups ⋮ On two problems related to cancellativity ⋮ Complexity results on the conjugacy problem for monoids
Cites Work
