Threshold circuits for iterated matrix product and powering
Mereghetti, Carlo ; Palano, Beatrice
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 39-46 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_1_39_0,
     author = {Mereghetti, Carlo and Palano, Beatrice},
     title = {Threshold circuits for iterated matrix product and powering},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {39-46},
     mrnumber = {1771128},
     zbl = {0962.68089},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_1_39_0}
}

Mereghetti, Carlo; Palano, Beatrice. Threshold circuits for iterated matrix product and powering. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 39-46. http://gdmltest.u-ga.fr/item/ITA_2000__34_1_39_0/

[1] D. A. Mix Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC1. J. Comp. System Sci. 44 (1992) 478-499. | MR 1163944 | Zbl 0757.68057

[2] S. A. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control. 64 (1985) 2-22. | MR 837088 | Zbl 0575.68045

[3] L. E. Dickson, Linear Groups with an Exposition of the Galois Field Theory. 1901. Reprinted by Dover (1958). | JFM 32.0128.01 | MR 104735 | Zbl 0082.24901

[4] S. Eilenberg, Automata, Languages, and Machines. Academic Press (1976). | Zbl 0359.94067

[5] W. Eberly, Very fast parallel polynomial arithmetic. SIAM J. Comput. 18 (1989) 955-976. | MR 1015268 | Zbl 0694.68029

[6] F. Gécseg, Products of Automata. Springer Verlag, Monogr. Theoret. Comput. Sci. EATCS Ser. 7 (1986). | MR 882544 | Zbl 0622.68049

[7] A. Hajnal, W. Maaß, P. Pudlák, M. Szegedy and G. Turán, Threshold circuits of bounded depth, in Proc. 28th IEEE Symposium on Foundations of Computer Science (1987) 99-110. Also in 7 . Comp. System Sci. 46 (1993) 129-154. | MR 1217153 | Zbl 0801.68052

[8] T. Hofmeister, Depth-efficient threshold circuits for arithmetic functions, edited by V. Roychowdhury, K.-Y. Siu and A. Orlitsky, Theoretical Advances in Neural Computation and Learning. Kluwer Academic (1994) 37-84. | Zbl 0835.68041

[9] C. Mereghetti and B. Palano, Threshold circuits for some matrix operations. Consequences on regular and probabilistic languages. Theoretical Computer Science - Proceedings of the 6th Italian Conference. World Scientific (1998) 216-227. | MR 1700322

[10] C. Mereghetti and B. Palano, The Parallel Complexity of Deterministic and Probabilistic Automata. Technical Report No. 242-99, Dipartimento di Scienze dell'Informazione. Università degli Studi di Milano (1999). Available at http://gongolo.usr.dsi.unimi.it/~mereghc/papers/TR_242-99.ps

[11] C. Mereghetti and B. Palano, Matrix Powering in Constant Depth. Technical Report No. 245-00, Dipartimento di Scienze dell'Informazione. Università degli Studi di Milano (2000) Available at http://gongolo.usr.dsi.unimi.it/~mereghc/papers/TR_245-00.ps

[12] V. Roychowdhury, K.-Y. Siu and A. Orlitsky, Neural models and spectral methods, edited by V. Roychowdhury, K.-Y. Siu and A. Orlitsky, Theoretical Advances in Neural Computation and Learning. Kluwer Academic (1994) 3-36. | Zbl 0835.68099

[13] G. Shilov, Linear Algebra. Prentice Hall (1971). Reprinted by Dover (1977). | MR 276252 | Zbl 0218.15003

[14] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser (1994). | MR 1269544 | Zbl 0816.68086

[15] I. Wegener, The Complexity of Boolean Functions. Teubner (1987). | MR 905473 | Zbl 0623.94018

[16] I. Wegener, Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions. Inform. Process. Lett. 46 (1993) 85-87. | MR 1219848 | Zbl 0770.68076