Threshold circuits for iterated matrix product and powering
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 1, pp. 39-46.
@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},
     pages = {39--46},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {1},
     year = {2000},
     mrnumber = {1771128},
     zbl = {0962.68089},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2000__34_1_39_0/}
}
TY  - JOUR
AU  - Mereghetti, Carlo
AU  - Palano, Beatrice
TI  - Threshold circuits for iterated matrix product and powering
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 39
EP  - 46
VL  - 34
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2000__34_1_39_0/
LA  - en
ID  - ITA_2000__34_1_39_0
ER  - 
%0 Journal Article
%A Mereghetti, Carlo
%A Palano, Beatrice
%T Threshold circuits for iterated matrix product and powering
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 39-46
%V 34
%N 1
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_2000__34_1_39_0/
%G en
%F 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) no. 1, pp. 39-46. http://www.numdam.org/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 | Zbl

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

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

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

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

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

[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 | Zbl

[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

[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

[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

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

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

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

[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 | Zbl