Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
loops; quasigroups; functional closure; solvability; quasidirect products; computational complexity
loops; quasigroups; functional closure; solvability; quasidirect products; computational complexity
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.
References:
[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. MR 0009962 | Zbl 0063.00039
[2] Barrington D.A., Straubing H., Thérien D.: Non-uniform automata over groups. Information and Computation 89 (1990), 109-132. MR 1080845
[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
[4] Bruck R.H.: Contributions to the theory of loops. Trans. Amer. Math. Soc 60 (1946), 245-354. MR 0017288 | Zbl 0061.02201
[5] Bruck R.H.: A Survey of Binary Systems. Springer-Verlag, 1966. MR 0093552 | Zbl 0141.01401
[6] Caussinus H., Lemieux F.: The complexity of computing over quasigroups. in Proc. 14th annual FST&TCS, 1994, pp.36-47. MR 1318016 | Zbl 1044.68679
[7] Chein O., Pflugfelder H.O., Smith J.D.H. (eds.): Quasigroups and Loops: Theory and Applications. Heldermann Verlag, 1990. MR 1125806 | Zbl 0719.20036
[8] Dénes J., Keedwell A.D.: Latin Squares and their Applications. English University Press, 1974. MR 0351850
[9] Goldmann M., Russell A.: Proc. 14th Annual IEEE Conference on Computational Complexity, 1999.
[10] Hall P.: The Theory of Groups. Macmillan, 1959. MR 0103215 | Zbl 0919.20001
[11] Lemieux F.: Finite Groupoids and their Applications to Computational Complexity. Ph.D. Thesis, School of Computer Science, McGill University, Montréal, 1996.
[12] Maurer W.D., Rhodes J.: A property of finite simple non-Abelian groups. Proc. Amer. Math. Soc. 16 (1965), 552-554. MR 0175971 | Zbl 0132.26903
[13] McKenzie R.: On minimal, locally finite varieties with permuting congruence relations. preprint, 1976.
[14] Moore C.: Predicting non-linear cellular automata quickly by decomposing them into linear ones. Physica D 111 (1998), 27-41. MR 1601494
[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.
[16] Papadimitriou C.H.: Computational Complexity. Addison-Wesley, 1994. MR 1251285 | Zbl 0833.68049
[17] Pflugfelder H.O.: Quasigroups and Loops: Introduction. Heldermann Verlag, 1990. MR 1125767 | Zbl 0715.20043
[18] Straubing H.: Families of recognizable sets corresponding to certain families of finite monoids. J. Pure Appl. Algebra 15 (1979), 305-318. MR 0537503
[19] Straubing H.: Representing functions by words over finite semigroups. Université de Montréal, Technical Report #838, 1992.
[20] Suzuki M.: Group Theory I. Springer-Verlag, 1982. MR 0648772 | Zbl 0472.20001
[21] Thérien D.: Classification of finite monoids: the language approach. Theor. Comp. Sci. 14 (1981), 195-208. MR 0614416
[22] Szendrei A.: Clones in Universal Algebra. Les Presses de L'Université de Montréal, 1986. MR 0859550 | Zbl 0603.08004
[23] Vesanen A.: Solvable groups and loops. J. Algebra 180 (1996), 862-876. MR 1379214 | Zbl 0853.20050
Search
Partner of
