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:
“Drug misuse is not a disease, it is a decision, like the decision to step out in front of a moving car. You would call that not a disease but an error of judgment.”
—Philip K. Dick (1928–1982)
“All problems are finally scientific problems.”
—George Bernard Shaw (1856–1950)