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:
“Moral choices do not depend on personal preference and private decision but on right reason and, I would add, divine order.”
—Basil Hume (b. 1923)
“The problems of all of humanity can only be solved by all of humanity.”
—Friedrich Dürrenmatt (1921–1990)