Abstract
This paper presents a general method for studying some quotients of the special linear group SL 2 over the integers, which are of fundamental interest in the field of statistical physics. Our method automatically helps in validating some conjectures due to physicists, such as conjectures stating that a set of equations completely describes a finite given quotient of SL 2. In a first step, we show that in the cases we are interested in, the usual presentation of finitely generated groups with some constant generators and a binary concatenation can be turned into an equivalent one with unary generators. In a second step, when the completion of the transformed set of equations terminates, we show how to compute directly the associated normal forms automaton. According to the presence of loops, we are able to decide the finiteness of the quotient, and to compute its cardinality. When the quotient is infinite, the automaton gives some hints on what kind of equations are needed in order to insure the finiteness of the quotient.
An extended version with complete proofs of this paper available at http://www.lri.fr/monate/rtatp-ext.ps.gz .
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bogaert, B., Tison, S.: Equality and disequality constraints on brother terms in tree automata. In: STACS 1992. LNCS, vol. 577, pp. 161–171. Springer, Heidelberg (1992)
Bündgen, R.: Term Completion versus Algebraic Completion. PhD thesis, Universität Tübingen (1991)
Contejean, E., Marché, C.: CiME: Completion Modulo E. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol. 1103, pp. 416–419. Springer, Heidelberg (1996), System Description available at http://www.lri.fr/~demons/cime.html
Coste, A., Gannon, T.: Congruence subgroups. Submitted, Electronic version available at http://xxx.lpthe.jussieu.fr/abs/math/9909080
Coste, A.: Quotients de SL 2(ℤ) pour les caractères. Preprint, Institut des Hautes Études Scientifiques (November 1997)
Dershowitz, N., Jouannaud, J.-P.: Rewrite systems. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 243–309. North-Holland, Amsterdam (1990)
Gilman, R.H.: Presentations of groups and monoids. Journal of Algebra 57, 544–554 (1979)
Holt, D.F.: Decision problems in finitely presented groups. In: Proceedings of the Euroconference “Computational Methods for Representations of Groups and Algebras”, Essen (April 1997)
Itzykson, C., Douffe, J.-M.: Théorie statistique des champs. Éditions du CNRS (1989)
Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebras. In: Leech, J. (ed.) Computational Problems in Abstract Algebra, pp. 263–297. Pergamon Press, Oxford (1970)
Lynch, C., Strogova, P.: Sour graphs for efficient completion. Discrete Mathematics and Theoretical Computer Science 2, 1–25 (1998)
Monate, B.: Automates de formes normales et réductibilité inductive. Journées du pôle Contraintes et programmation logique, 21–31, Rennes, PRC/GDR Programmation du CNRS (November 1997)
Stillwell, J.: The word problem and the isomorphism problem for groups. Bulletin of the American Mathematical Society 6(1), 33–56 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Contejean, E., Coste, A., Monate, B. (2000). Rewriting Techniques in Theoretical Physics. In: Bachmair, L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10721975_6
Download citation
DOI: https://doi.org/10.1007/10721975_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67778-9
Online ISBN: 978-3-540-44980-5
eBook Packages: Springer Book Archive