| Title:
|
Polyabelian loops and Boolean completeness (English) |
| Author:
|
Lemieux, François |
| Author:
|
Moore, Cristopher |
| Author:
|
Thérien, Denis |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
41 |
| Issue:
|
4 |
| Year:
|
2000 |
| Pages:
|
671-686 |
| . |
| Category:
|
math |
| . |
| Summary:
|
We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property {\it Boolean completeness\/}. It is a generalization of functional completeness, and is intimately connected to the computational complexity of various questions about expressions, circuits, and equations defined over the loop. We say that a loop is {\it polyabelian\/} if it is an iterated affine quasidirect product of Abelian groups; polyabelianness coincides with solvability for groups, and lies properly between nilpotence and solvability for loops. Our main result is that a loop is Boolean-complete if and only if it is not polyabelian. Since groups are Boolean-complete if and only if they are not solvable, this shows that polyabelianness, for these purposes, is the appropriate generalization of solvability to loops. (English) |
| Keyword:
|
loops |
| Keyword:
|
quasigroups |
| Keyword:
|
functional closure |
| Keyword:
|
solvability |
| Keyword:
|
quasidirect products |
| Keyword:
|
computational complexity |
| MSC:
|
03G05 |
| MSC:
|
06E30 |
| MSC:
|
17A01 |
| MSC:
|
17X08 |
| MSC:
|
20N05 |
| MSC:
|
68Q15 |
| MSC:
|
68W30 |
| MSC:
|
94C10 |
| idZBL:
|
Zbl 1051.20033 |
| idMR:
|
MR1800174 |
| . |
| Date available:
|
2009-01-08T19:06:20Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119201 |
| . |
| Reference:
|
[1] Albert A.A.: Quasigroups I.Trans. Amer. Math. Soc. 54 (1943), 507-519 and {Quasigroup II}, Trans. Amer. Math. Soc. 55 (1944), 401-419. Zbl 0063.00039, MR 0009962 |
| Reference:
|
[2] Barrington D.A., Straubing H., Thérien D.: Non-uniform automata over groups.Information and Computation 89 (1990), 109-132. MR 1080845 |
| Reference:
|
[3] Barrington D., Thérien D.: Finite monoids and the fine structure of $NC^1$.Journal of the ACM 35 (1988), 941-952. MR 1072406 |
| Reference:
|
[4] Bruck R.H.: Contributions to the theory of loops.Trans. Amer. Math. Soc 60 (1946), 245-354. Zbl 0061.02201, MR 0017288 |
| Reference:
|
[5] Bruck R.H.: A Survey of Binary Systems.Springer-Verlag, 1966. Zbl 0141.01401, MR 0093552 |
| Reference:
|
[6] Caussinus H., Lemieux F.: The complexity of computing over quasigroups.in Proc. 14th annual FST&TCS, 1994, pp.36-47. Zbl 1044.68679, MR 1318016 |
| Reference:
|
[7] Chein O., Pflugfelder H.O., Smith J.D.H. (eds.): Quasigroups and Loops: Theory and Applications.Heldermann Verlag, 1990. Zbl 0719.20036, MR 1125806 |
| Reference:
|
[8] Dénes J., Keedwell A.D.: Latin Squares and their Applications.English University Press, 1974. MR 0351850 |
| Reference:
|
[9] Goldmann M., Russell A.: Proc. 14th Annual IEEE Conference on Computational Complexity, 1999.. |
| Reference:
|
[10] Hall P.: The Theory of Groups.Macmillan, 1959. Zbl 0919.20001, MR 0103215 |
| Reference:
|
[11] Lemieux F.: Finite Groupoids and their Applications to Computational Complexity.Ph.D. Thesis, School of Computer Science, McGill University, Montréal, 1996. |
| Reference:
|
[12] Maurer W.D., Rhodes J.: A property of finite simple non-Abelian groups.Proc. Amer. Math. Soc. 16 (1965), 552-554. Zbl 0132.26903, MR 0175971 |
| Reference:
|
[13] McKenzie R.: On minimal, locally finite varieties with permuting congruence relations.preprint, 1976. |
| Reference:
|
[14] Moore C.: Predicting non-linear cellular automata quickly by decomposing them into linear ones.Physica D 111 (1998), 27-41. MR 1601494 |
| Reference:
|
[15] Moore C., Thérien D., Lemieux F., Berman J., Drisko A.: Circuits and expressions with non-associative gates.to appear in J. Comput. System Sci. |
| Reference:
|
[16] Papadimitriou C.H.: Computational Complexity.Addison-Wesley, 1994. Zbl 0833.68049, MR 1251285 |
| Reference:
|
[17] Pflugfelder H.O.: Quasigroups and Loops: Introduction.Heldermann Verlag, 1990. Zbl 0715.20043, MR 1125767 |
| Reference:
|
[18] Straubing H.: Families of recognizable sets corresponding to certain families of finite monoids.J. Pure Appl. Algebra 15 (1979), 305-318. MR 0537503 |
| Reference:
|
[19] Straubing H.: Representing functions by words over finite semigroups.Université de Montréal, Technical Report #838, 1992. |
| Reference:
|
[20] Suzuki M.: Group Theory I..Springer-Verlag, 1982. Zbl 0472.20001, MR 0648772 |
| Reference:
|
[21] Thérien D.: Classification of finite monoids: the language approach.Theor. Comp. Sci. 14 (1981), 195-208. MR 0614416 |
| Reference:
|
[22] Szendrei A.: Clones in Universal Algebra.Les Presses de L'Université de Montréal, 1986. Zbl 0603.08004, MR 0859550 |
| Reference:
|
[23] Vesanen A.: Solvable groups and loops.J. Algebra 180 (1996), 862-876. Zbl 0853.20050, MR 1379214 |
| . |
