E. Allender, W. Hesse, and D. A. Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, J. Comput. System Sci, vol.65, issue.4, pp.695-716, 2001.

E. Allender, P. Bürgisser, J. Kjeldgaard-pedersen, and P. B. Miltersen, On the Complexity of Numerical Analysis, SIAM Journal on Computing, vol.38, issue.5, pp.1987-200609, 2008.
DOI : 10.1137/070697926

P. W. Beame, S. A. Cook, and H. J. Hoover, Log Depth Circuits for Division and Related Problems, SIAM Journal on Computing, vol.15, issue.4, pp.994-1003, 1986.
DOI : 10.1137/0215070

P. Berman, M. Karpinski, L. L. Larmore, W. Plandowski, and W. Rytter, On the complexity of pattern matching for highly compressed two-dimensional texts, Combinatorial pattern matching, pp.40-51, 1997.
DOI : 10.1007/3-540-63220-4_48

J. Berstel and L. Boasson, Formal properties of XML grammars and languages, Acta Informatica, vol.38, issue.9, pp.649-671, 2002.
DOI : 10.1007/s00236-002-0085-4
URL : https://hal.archives-ouvertes.fr/hal-00619461

A. Bertoni, G. Mauri, and N. Sabadini, A characterization of the class of functions computable in polynomial time on Random Access Machines, Proceedings of the thirteenth annual ACM symposium on Theory of computing , STOC '81, pp.168-176, 1981.
DOI : 10.1145/800076.802470

A. Bertoni, C. Choffrut, and R. Radicioni, The Inclusion Problem of Context-Free Languages: Some Tractable Cases, Developments in language theory, pp.103-112, 2009.
DOI : 10.1007/3-540-47849-3_3

L. Blum, M. Shub, F. Cucker, and S. Smale, Complexity and real computation, 1997.
DOI : 10.1007/978-1-4612-0701-6

R. V. Book and F. Otto, String-rewriting systems, 1993.

J. Canny, The complexity of robot motion planning, volume 1987 of ACM Doctoral Dissertation Awards, 1988.

J. Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC '88, pp.460-469, 1988.
DOI : 10.1145/62212.62257

P. Cartier and D. Foata, Probì emes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, issue.85, 1969.
DOI : 10.1007/bfb0079468

C. Duboc, Commutations dans les mono¨?desmono¨?des libres: un cadre théorique pour l'´ etude du parallélisme, 1986.

K. Etessami and M. Yannakakis, On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract), 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp.113-123, 2007.
DOI : 10.1109/FOCS.2007.39

M. Garey, R. Graham, and D. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing , STOC '76, pp.10-22, 1976.
DOI : 10.1145/800113.803626

M. R. Garey, D. S. Johnson, I. W. Computers, and C. Freeman, A guide to the theory of NP-completeness, Series of Books in the Mathematical Sci- ences, 1979.

A. Gascón, G. Godoy, and M. Schmidt-schauß, Unification with Singleton Tree Grammars, Rewriting Techniques and Applications, pp.365-379, 2009.
DOI : 10.1145/321250.321253

L. Gasieniec, M. Karpinski, W. Plandowski, and W. Rytter, Efficient algorithms for Lempel-Ziv encoding, Lecture Notes in Computer Science, vol.1097, pp.392-403, 1996.
DOI : 10.1007/3-540-61422-2_148

S. A. Greibach and E. P. Friedman, Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem, Journal of the ACM, vol.27, issue.4, pp.675-700, 1980.
DOI : 10.1145/322217.322224

W. Hesse, E. Allender, and D. M. Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences, vol.65, issue.4, pp.695-716, 2002.
DOI : 10.1016/S0022-0000(02)00025-9

J. E. Hopcroft, On the equivalence and containment problems for context-free languages, Mathematical Systems Theory, vol.113, issue.2, pp.119-124, 1969.
DOI : 10.1007/BF01746517

H. Hunt, I. , R. Stearns, and M. Marathe, Relational representability, local reductions, and the complexity of generalized satisfiability problems, 2000.

D. E. Knuth, A characterization of parenthesis languages, Information and Control, vol.11, issue.3, pp.269-289, 1967.
DOI : 10.1016/S0019-9958(67)90564-5

A. N. Kolmogorov, Three approaches to the quantitative definition of information. Internat, J. Comput. Math, vol.2, pp.157-168, 1968.

E. Lehman and A. Shelat, Approximation algorithms for grammar-based compression, SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pp.205-212, 2002.

Y. Lifshits, Processing Compressed Texts: A Tractability Border, Combinatorial Pattern Matching, pp.228-240, 2007.
DOI : 10.1007/978-3-540-73437-6_24

M. Lohrey, Word Problems and Membership Problems on Compressed Words, SIAM Journal on Computing, vol.35, issue.5, pp.1210-1240, 2006.
DOI : 10.1137/S0097539704445950

A. Mazurkiewicz, Concurrent Program Schemes and their Interpretations, DAIMI Report Series, vol.6, issue.78, 1977.
DOI : 10.7146/dpb.v6i78.7691

A. R. Meyer and L. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, 13th Annual Symposium on Switching and Automata Theory (swat 1972), pp.125-129, 1972.
DOI : 10.1109/SWAT.1972.29

J. Nash, Non-Cooperative Games, The Annals of Mathematics, vol.54, issue.2, pp.286-295, 1951.
DOI : 10.2307/1969529

W. Plandowski, Testing equivalence of morphisms on context-free languages, Algorithms?ESA '94, pp.460-470, 1994.
DOI : 10.1007/BFb0049431

A. Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Mathematicheskie Zametki, vol.41, issue.4, pp.598-607, 1987.

J. H. Reif and S. R. Tate, On Threshold Circuits and Polynomial Computation, SIAM Journal on Computing, vol.21, issue.5, pp.896-908, 1992.
DOI : 10.1137/0221053

W. Rytter, Application of Lempel???Ziv factorization to the approximation of grammar-based compression, Theoretical Computer Science, vol.302, issue.1-3, pp.211-222, 2003.
DOI : 10.1016/S0304-3975(02)00777-6

A. Schönhage, On the power of random access machines, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, pp.520-529, 1979.
DOI : 10.1007/3-540-09510-1_42

P. Tiwari, A problem that is easier to solve on the unit-cost algebraic RAM, Journal of Complexity, vol.8, issue.4, pp.393-397, 1992.
DOI : 10.1016/0885-064X(92)90003-T

J. Torán, Complexity classes defined by counting quantifiers, Journal of the ACM, vol.38, issue.3, pp.753-774, 1991.
DOI : 10.1145/116825.116858

L. G. Valiant, Decision procedures for families of deterministic pushdown automata, 1973.

J. Von-neumann, O. Morgenstern, and N. J. , Theory of Games and Economic Behavior, 1947.

K. W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, vol.3, issue.3, pp.325-356, 1986.
DOI : 10.1007/BF00289117