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:
“There are many things children accept as “grown-up things” over when they have no control and for which they have no responsibility—for instance, weddings, having babies, buying houses, and driving cars. Parents who are separating really need to help their children put divorce on that grown-up list, so that children do not see themselves as the cause of their parents’ decision to live apart.”
—Fred Rogers (20th century)
“The problems of this world are only truly solved in two ways: by extinction or duplication.”
—Susan Sontag (b. 1933)