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:
“Every decision is liberating, even if it leads to disaster. Otherwise, why do so many people walk upright and with open eyes into their misfortune?”
—Elias Canetti (b. 1905)
“The problems of victory are more agreeable than the problems of defeat, but they are no less difficult.”
—Winston Churchill (1874–1965)