ON CONFLUENT SEMICOMMUTATIONS - DECIDABILITY AND COMPLEXITY RESULTS

The subject of this paper is the confluence of finite semi-commutation systems. Confluence of such systems is proved to be decidable propert y. Existence of a finite complete presentation of a trace monoid using rules only from another given trace monoid is proved to be reducible to the existence of a confluent semi-commutation system. Complexity re sults related to the preceding problems are proved: deciding the exist ence of finite complete presentations is SIGMA2P-complete, whereas dec iding confluence of semi-commutation systems is Co-NP-complete. Additi onally, an open problem about trace synchronizations is solved: The lo cal checking property is Co-NP-complete. (C) 1994 Academic Press, Inc.