Automatic Semigroup - Decision Problems

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:

    “The decision to have a child is both a private and a public decision, for children are our collective future.”
    —Sylvia Ann Hewitt (20th century)

    “In many ways, life becomes simpler [for young adults]. . . . We are expected to solve only a finite number of problems within a limited range of possible solutions. . . . It’s a mental vacation compared with figuring out who we are, what we believe, what we’re going to do with our talents, how we’re going to solve the social problems of the globe . . .and what the perfect way to raise our children will be.”
    —Roger Gould (20th century)