Polyabelian loops and Boolean completeness

François Lemieux; Cristopher Moore; Denis Thérien

Commentationes Mathematicae Universitatis Carolinae (2000)

  • Volume: 41, Issue: 4, page 671-686
  • ISSN: 0010-2628

Abstract

top
We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property 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 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.

How to cite

top

Lemieux, François, Moore, Cristopher, and Thérien, Denis. "Polyabelian loops and Boolean completeness." Commentationes Mathematicae Universitatis Carolinae 41.4 (2000): 671-686. <http://eudml.org/doc/248644>.

@article{Lemieux2000,
abstract = {We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property 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 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.},
author = {Lemieux, François, Moore, Cristopher, Thérien, Denis},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {loops; quasigroups; functional closure; solvability; quasidirect products; computational complexity; loops; quasigroups; functional closures; solvability; Boolean completeness; quasidirect products; computational complexity; pseudovarieties},
language = {eng},
number = {4},
pages = {671-686},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Polyabelian loops and Boolean completeness},
url = {http://eudml.org/doc/248644},
volume = {41},
year = {2000},
}

TY - JOUR
AU - Lemieux, François
AU - Moore, Cristopher
AU - Thérien, Denis
TI - Polyabelian loops and Boolean completeness
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2000
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 41
IS - 4
SP - 671
EP - 686
AB - We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property 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 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.
LA - eng
KW - loops; quasigroups; functional closure; solvability; quasidirect products; computational complexity; loops; quasigroups; functional closures; solvability; Boolean completeness; quasidirect products; computational complexity; pseudovarieties
UR - http://eudml.org/doc/248644
ER -

References

top
  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. (1943) Zbl0063.00039MR0009962
  2. Barrington D.A., Straubing H., Thérien D., Non-uniform automata over groups, Information and Computation 89 (1990), 109-132. (1990) MR1080845
  3. Barrington D., Thérien D., Finite monoids and the fine structure of N C 1 , Journal of the ACM 35 (1988), 941-952. (1988) MR1072406
  4. Bruck R.H., Contributions to the theory of loops, Trans. Amer. Math. Soc 60 (1946), 245-354. (1946) Zbl0061.02201MR0017288
  5. Bruck R.H., A Survey of Binary Systems, Springer-Verlag, 1966. Zbl0141.01401MR0093552
  6. Caussinus H., Lemieux F., The complexity of computing over quasigroups, in Proc. 14th annual FST&TCS, 1994, pp.36-47. Zbl1044.68679MR1318016
  7. Chein O., Pflugfelder H.O., Smith J.D.H. (eds.), Quasigroups and Loops: Theory and Applications, Heldermann Verlag, 1990. Zbl0719.20036MR1125806
  8. Dénes J., Keedwell A.D., Latin Squares and their Applications, English University Press, 1974. MR0351850
  9. Goldmann M., Russell A., Proc. 14th Annual IEEE Conference on Computational Complexity, 1999, . 
  10. Hall P., The Theory of Groups, Macmillan, 1959. Zbl0919.20001MR0103215
  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. (1965) Zbl0132.26903MR0175971
  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. (1998) MR1601494
  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. Zbl0833.68049MR1251285
  17. Pflugfelder H.O., Quasigroups and Loops: Introduction, Heldermann Verlag, 1990. Zbl0715.20043MR1125767
  18. Straubing H., Families of recognizable sets corresponding to certain families of finite monoids, J. Pure Appl. Algebra 15 (1979), 305-318. (1979) MR0537503
  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. Zbl0472.20001MR0648772
  21. Thérien D., Classification of finite monoids: the language approach, Theor. Comp. Sci. 14 (1981), 195-208. (1981) MR0614416
  22. Szendrei A., Clones in Universal Algebra, Les Presses de L'Université de Montréal, 1986. Zbl0603.08004MR0859550
  23. Vesanen A., Solvable groups and loops, J. Algebra 180 (1996), 862-876. (1996) Zbl0853.20050MR1379214

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.