Complexity results on the conjugacy problem for monoids

DOI10.1016/0304-3975(85)90016-7zbMATH Open0588.03022OpenAlexW1999125908MaRDI QIDQ1073015FDOQ1073015

Authors: Friedrich Otto, Paliath Narendran 

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90016-7

Recommendations

• Complexity of the generalized conjugacy problem
• The Knuth-Bendix algorithm and the conjugacy problem in monoids.
• Decidability and independence of conjugacy problems in finitely presented monoids
• Computational complexity and the conjugacy problem
• Computations over finite monoids and their test complexity
• Complexity issues of checking identities in finite monoids
• scientific article; zbMATH DE number 1303030
• scientific article; zbMATH DE number 1504638
• Generic complexity of finitely presented monoids and semigroups
• Computational complexity of some problems involving congruences on algebras

zbMATH Keywords

Church-Rosser propertyThue system

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Complexity of computation (including implicit computational complexity) (03D15) Free semigroups, generators and relations, word problems (20M05) Other degrees and reducibilities in computability and recursion theory (03D30) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

• Title not available (Why is that?)
• Relationships between nondeterministic and deterministic tape complexities
• Title not available (Why is that?)
• On the computational power of pushdown automata
• Title not available (Why is that?)
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursive unsolvability of a problem of Thue
• Title not available (Why is that?)
• Title not available (Why is that?)
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• Confluent and Other Types of Thue Systems
• Title not available (Why is that?)
• Monadic Thue systems
• Infinite regular Thue systems
• Decidable sentences of Church-Rosser congruences
• Recursively enumerable degress and the conjugacy problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Church-Rosser property and special Thue systems
• Title not available (Why is that?)

Cited In (19)

• Incidence monoids: automorphisms and complexity
• On equations and first-order theory of one-relator monoids
• On two problems related to cancellativity
• Thue systems as rewriting systems
• Decision problems for finite special string-rewriting systems that are confluent on some congruence class
• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Knuth-Bendix algorithm and the conjugacy problem in monoids.
• On deciding whether a monoid is a free monoid or is a group
• Title not available (Why is that?)
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Title not available (Why is that?)
• About the descriptive power of certain classes of finite string-rewriting systems
• Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Decidability and independence of conjugacy problems in finitely presented monoids
• Deciding conjugacy in Sylvester monoids and other homogeneous monoids.
• Conjugacy in monoids with a special Church-Rosser presentation is decidable

This page was built for publication: Complexity results on the conjugacy problem for monoids

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