Decision Problems
Like automatic groups, automatic semigroups have word problem solvable in quadratic time. Kambites & Otto (2006) showed that it is undecidable whether an element of an automatic monoid possesses a right inverse.
Cain (2006) proved that both cancellativity and left-cancellativity are undecidable for automatic semigroups. On the other hand, right-cancellativity is decidable for automatic semigroups (Silva & Steinberg 2004).
Read more about this topic: Automatic Semigroup
Famous quotes containing the words decision and/or problems:
“I know my fate. One day my name will be tied to the memory of something monstrous—a crisis without equal on earth, the most profound collision of conscience, a decision invoked against everything that had previously been believed, demanded, sanctified. I am no man, I am dynamite!”
—Friedrich Nietzsche (1844–1900)
“If family communication is good, parents can pick up the signs of stress in children and talk about it before it results in some crisis. If family communication is bad, not only will parents be insensitive to potential crises, but the poor communication will contribute to problems in the family.”
—Donald C. Medeiros (20th century)