Hostname: page-component-7b7567c8c-8tzhz Total loading time: 0 Render date: 2026-11-19T21:13:41.385Z Has data issue: false hasContentIssue false

Undecidability of the identity problem for finite semigroups

Published online by Cambridge University Press:  12 March 2014

Douglas Albert
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720
Robert Baldinger
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720, E-mail: baldinger@math.berkeley.edu
John Rhodes
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720, E-mail: rhodes@math.berkeley.edu

Extract

In 1947 E. Post [28] and A. A. Markov [18] independently proved the undecidability of the word problem (or the problem of deducibility of relations) for semigroups. In 1968 V. L. Murskil [23] proved the undecidability of the identity problem (or the problem of deducibility of identities) in semigroups.

If we slightly generalize the statement of these results we can state many related results in the literature and state our new results proved here. Let V denote either a (Birkhoff) variety of semigroups or groups or a pseudovariety of finite semigroups. By a very well-known theorem a (Birkhoff) variety is defined by equations or equivalently closed under substructure, surmorphisms and all products; see [7]. It is also well known that V is a pseudovariety of finite semigroups iff V is closed under substructure, surmorphism and finite products, or, equivalently, determined eventually by equations w1 = w1′, w2 = w2′, w3 = w3′,… (where the finite semigroup S eventually satisfies these equations iff there exists an n, depending on S, such that S satisfies Wj = Wj′ for j ≥ n). See [8] and [29]. All semigroups form a variety while all finite semigroups form a pseudovariety.

We now consider a table (see the next page). In it, for example, the box denoting the “word” (identity) problem for the psuedovariety V” means, given a finite set of relations (identities) E and a relation (identity) u = ν, the problem of whether it is decidable that E implies u = ν inside V.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable