Bounded-width polynomial size branching programs recognize exactly those languages in NC 1, Bovet and P. Crescenzi. Introduction to the Theory of Complexity. International Series in Computer Science, pp.150-164, 1989. ,
A uniform approach to define complexity classes, Theoretical Computer Science, vol.104, issue.2, pp.263-283, 1992. ,
DOI : 10.1016/0304-3975(92)90125-Y
Structural Complexity I. Texts in Theoretical Computer Science, 1995. ,
On uniformity within NC1, Journal of Computer and System Sciences, vol.41, issue.3, pp.274-306, 1990. ,
DOI : 10.1016/0022-0000(90)90022-D
On input read-modes of alternating Turing machines, Theoretical Computer Science, vol.148, issue.1, pp.33-55, 1995. ,
DOI : 10.1016/0304-3975(94)00253-F
Alternation, Journal of the ACM, vol.28, issue.1, pp.114-133, 1981. ,
DOI : 10.1145/322234.322243
Nondeterministic NC/sup 1/ computation, Proceedings of Computational Complexity (Formerly Structure in Complexity Theory), pp.200-212, 1998. ,
DOI : 10.1109/CCC.1996.507664
Locally definable acceptance types for polynomial time machines, Proceedings 9th Symposium on Theoretical Aspects of Computer Science, pp.199-207, 1992. ,
Complexity classes defined via k-valued functions, Proceedings 9th Structure in Complexity Theory, pp.224-234, 1994. ,
On the power of polynomial time bit-reductions, Proceedings 8th Structure in Complexity Theory, pp.200-207, 1993. ,
Introduction to Automata Theory, Languages, and Computation . Addison-Wesley Series in Computer Science, 1979. ,
Logspace and logtime leaf languages, Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory, pp.21-33, 1996. ,
DOI : 10.1109/SCT.1994.315799
Computational Complexity Handbook of Formal Languages, volume I, 1994. ,
Gap-languages and log-time complexity classes, Theoretical Computer Science, vol.188, issue.1-2, pp.101-116, 1997. ,
DOI : 10.1016/S0304-3975(96)00288-5
Borel sets and circuit complexity, Proceedings of the 15th Symposium on Theory of Computing, pp.61-69, 1983. ,
Relativizable and non-relativizable theorems in the polynomial theory of algorithms, Izvestija Rossijskoj Akademii Nauk, vol.57, pp.51-90, 1993. ,
Regular languages, Handbook of Formal Languages, pp.41-110, 1997. ,