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:
“Concision in style, precision in thought, decision in life.”
—Victor Hugo (1802–1885)
“I respect guilt. It is a dangerous but sometimes useful beast. The guilt that made me want to solve all my children’s problems meant trouble. The guilt that made me question my role in our mother-daughter squabbles proved helpful. Yes, I care about my kids’ problems, and I long to make suggestions. But these days I wait for children to ask for help, and I give it sparingly. Some things can’t be fixed, and I tell them so.”
—Susan Ferraro (20th century)