Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Decidability and independence of conjugacy problems in finitely presented monoids
Araújo J., Kinyon M., Konieczny J., Malheiro A. Theoretical Computer Science731 (C):88-98,2018.Type:Article
Date Reviewed: Jul 20 2018

In a group, two elements a and b are conjugate if there is some g with gag-1 = b. Conjugacy is an equivalence relation and can be used to partition a group into equivalence classes whose elements are “similar”; the study of conjugacy classes can thus reveal important features of a group’s structure.

The present paper studies various generalizations of conjugacy that can also be applied to monoids, because they do not rely on the existence of inverses. Previously, conjugacy relations ~p and ~0 were proposed, but ~p is only an equivalence relation on free monoids and ~0 reduces to the universal relation on monoids with zeros. In contrast, the authors propose a relation ~c that is applicable to arbitrary monoids. While the conjugacy problem for finitely presented groups is undecidable, the paper studies the decidability and interdependence properties of the various conjugacy notions in the class of polycyclic monoids. In particular, it is shown that ~c is stronger than ~p, that c- and p-conjugacy are decidable in linear time, and that some decidability problems are independent of each other while others are not.

The paper is of a foundational nature; it widens the knowledge on decidability and complexity in the theory of monoids. Unfortunately, it does not indicate which conjugacy notion is applicable to which kind of application domain and is thus of interest mainly to specialists. Open problems to be addressed include whether the c-conjugacy problem is decidable in certain other monoid classes.

Reviewer:  Wolfgang Schreiner Review #: CR146163 (1811-0581)
Bookmark and Share
  Featured Reviewer  
 
Decision Problems (F.4.2 ... )
 
 
Complexity Hierarchies (F.1.3 ... )
 
 
General (G.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Decision Problems": Date
Ambiguity and decision problems concerning number systems
Karel I., Salomaa A. Information and Control 56(3): 139-153, 1983. Type: Article
Mar 1 1985
The problems of cyclic equality and conjugacy for finite complete rewriting systems
Narendran P., Otto F. Theoretical Computer Science 47(1): 27-38, 1986. Type: Article
Jun 1 1988
Parallel time O (log n) recognition of unambiguous context-free languages
Rytter W. Information and Computation 73(1): 75-86, 1987. Type: Article
Mar 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy