The complexity of computing over quasigroups

In [7] the notions of recognition by semigroups and by programs over semigroups were extended to groupoids. As a consequence of this transformation, the induced classes of languages became CFL instead of REG, in the first case, and SAC1 instead of NC1 in the second case. In this paper, we investigate the classes obtained when the groupoids are restricted to be quasigroups (i.e. the multiplication table forms a latin square). We prove that languages recognized by quasigroups are regular and that programs over quasigroups characterize NC1. We introduce the notions of linear recognition by semigroups and by programs over semigroups. This leads to a new characterization of the linear context-free languages and NL. Here again, when quasigroups are used, only languages in REG and NC1 can be obtained. We also consider the problem of evaluating a well-parenthesized expression over a finite loop (a quasigroup with an identity). This problem is in NC1 for any finite loop, and we give algebraic conditions for its completeness. In particular, we prove that it is sufficient that the loop be noasolvable, extending a well-known theorem of Barrington.