[Information and Computation, December 1990, pp. 180-198]
Properties of Words in a Free Partially Commutative Monoid
Hai-Ning Liu, Celia Wrathall, and Kenneth A. Zeger
Abstract
We examine several properties of words in a Free Partially Commutative
Monoid. The Word Reconstruction Problem and The Reconstructibility
Problem are presented and shown to be decidable, each with linear-time
algorithms. The notions of congruential prefix and congruential root
of a word in Σ* are defined, and several results analogous
to the case of a free monoid are proven. The Generalized Word Problem
in an FPCM is solved with a quadratic time algorithm. Polynomial-time
algorithms are given deciding the Conjugacy and Cyclic Equality Problems.