×

The complexity of computing over quasigroups. (English) Zbl 1044.68679

Thiagarajan, P. S. (ed.), Foundations of software technology and theoretical computer science. 14th conference, Madras, India, December 15-17, 1994. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-58715-2 /SC). Lect. Notes Comput. Sci. 880, 36-47 (1994).
Summary: In a paper by F. Bédard, F. Lemieux and P. McKenzie [Theor. Comput. Sci. 107, 31–61 (1993; Zbl 0764.68040)] 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 \(\text{SAC}^1\) instead of \(\text{NC}^1\) in the second case. In this paper, we investigate the classes obtained when the groupoids are restricted to the 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 \(\text{NC}^1\). 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 \(\text{NC}^1\) 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 \(\text{NC}^1\) for any finite loop, and we give algebraic conditions for its completeness. In particular, we prove that it is sufficient that the loop be nonsolvable, extending a well-known theorem of Barrington.
For the entire collection see [Zbl 0802.00044].

MSC:

68Q70 Algebraic theory of languages and automata
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0764.68040
PDFBibTeX XMLCite