Cancellativity in finitely presented semigroups.

*(English)*Zbl 0682.20046This paper considers whether or not cancellativity is decidable in finitely presented semigroups answering questions raised in a paper by R. Book [J. Symb. Comput. 3, 39-68 (1987; Zbl 0638.68091)].

Cancellativity is shown to be undecidable in semigroups presented by Thue systems even if the systems are monadic. In general, cancellativity is even undecidable in semigroups presented by Church-Rosser Thue systems, but decidable if the system is monadic. For semigroups which are presented by commutative Thue systems cancellativity is decidable; the negation is in NP if the system is canonical.

Cancellativity is shown to be undecidable in semigroups presented by Thue systems even if the systems are monadic. In general, cancellativity is even undecidable in semigroups presented by Church-Rosser Thue systems, but decidable if the system is monadic. For semigroups which are presented by commutative Thue systems cancellativity is decidable; the negation is in NP if the system is canonical.

Reviewer: B.L.Madison

##### MSC:

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

03D03 | Thue and Post systems, etc. |

03D40 | Word problems, etc. in computability and recursion theory |

20M35 | Semigroups in automata theory, linguistics, etc. |

68Q45 | Formal languages and automata |

##### Keywords:

cancellativity; finitely presented semigroups; undecidable; semigroups presented by Thue systems; Church-Rosser Thue systems; commutative Thue systems
PDF
BibTeX
XML
Cite

\textit{P. Narendran} and \textit{C. Ó'Dúnlaing}, J. Symb. Comput. 7, No. 5, 457--472 (1989; Zbl 0682.20046)

Full Text:
DOI

##### References:

[1] | Adjan, S.I., Defining relations and aigorithmic problems for groups and semigroups, (), 1967 |

[2] | Book, R., Confluent and other types of thue systems, J. assoc. comput. math., 29, 171-182, (1982) · Zbl 0478.68032 |

[3] | Book, R., Decidable sentences of church-rosser congruences, Theor. comp. sci., 24, 301-312, (1983) · Zbl 0525.68015 |

[4] | Book, R., Thue systems as rewriting systems, J. symbolic computation, 3, 39-68, (1987) · Zbl 0638.68091 |

[5] | Book, R.; Ó’Dúnlain, C., Testing for the church-rosser property, Theor. comp. sci., 16, 223-229, (1981) · Zbl 0479.68035 |

[6] | Clifford, A.H.; Preston, G.B., (), Vols. I, II |

[7] | Fischer, M.J.; Rabin, M.O., Super-exponential complexity of Presburger arithmetic, (), 27-41 |

[8] | Kandri-Rody, A.; Kapur, D., Computing the Gröbner basis of a polynomial ideal over integers, (), 436-451 |

[9] | Kandri-Rody, A.; Kapur, D.; Narendran, P., An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebras, (), 345-364 |

[10] | Kapur, D.; Narendran, P., The Knuth-bendix completion procedure and thue systems, SIAM J. comp., 14, 4, 1052-1072, (1985) · Zbl 0576.68010 |

[11] | Lankford, D.S.; Ballantyne, A.M., Decision procedures for simple equational theories with commutative-associate axioms: complete sets of commutative-associative reductions, () · Zbl 0449.20059 |

[12] | Lyndon, R.; Schupp, P., () |

[13] | Markov, A., Impossibility of algorithms for recognizing some properties of associative systems, Dokl. akad. nauk SSSR, 77, 953-956, (1951) |

[14] | Mostowski, A., Review of Markov’s paper, J. symb. logic, 17, 151-152, (1952) |

[15] | Narendran, P., Church-rosser and related thue systems, (), 12181 |

[16] | Narendran, P.; Ó’Dúnlaing, C.; Rolletschek, H., Complexity of certain decision problems about congruential languages, J. comp. system sci., 30, 343-358, (1985) · Zbl 0607.68055 |

[17] | Narendran, P.; Otto, F., Some polynomial-time algorithms for finite monadic church-rosser thue systems, (1987), (in preparation) |

[18] | Nivat, M.; M., Benois, Congruences parfaites et quasi-parfaites, () · Zbl 0338.02018 |

[19] | Ó’Dúnlaing, C., Undecidable questions related to church-rosser thue systems, Theor. comp. sci., 23, 339-345, (1983) · Zbl 0512.03019 |

[20] | Otto, F., Deciding algebraic properties of monoids presented by finite church-rosser thue systems, (), 95-106 |

[21] | Papadimitriou, C.H.; Steiglitz, K., () |

[22] | Szmielew, W., Elementary properties of abelian groups, Fund. math., 41, 203-271, (1954) · Zbl 0064.00803 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.