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)
“I’m no good at being noble, but it doesn’t take much to see that the problems of three little people don’t amount to a hill of beans in this crazy world. Someday you’ll understand that.”
—Julius J. Epstein, U.S. screenwriter, Philip Epstein, screenwriter, Howard Koch, screenwriter, and Michael Curtiz. Rick Blaine (Humphrey Bogart)