M. Anthony, Threshold Functions, Decision Lists, and the Representation of Boolean Functions, 1996.

S. Amoroso and Y. Patt, Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, Journal of Computer and System Sciences, vol.6, issue.5, pp.448-464, 1972.
DOI : 10.1016/S0022-0000(72)80013-8

R. J. Bagley and L. Glass, Counting and Classifying Attractors in High Dimensional Dynamical Systems, Journal of Theoretical Biology, vol.183, issue.3, pp.269-284, 1996.
DOI : 10.1006/jtbi.1996.0220

F. Barahona, On the computational complexity of Ising spin glass models, Journal of Physics A: Mathematical and General, vol.15, issue.10, pp.3241-3253, 1982.
DOI : 10.1088/0305-4470/15/10/028

C. Barrett, H. B. Hunt, I. , M. V. Marathe, S. S. Ravi et al., Dichotomy Results for Sequential Dynamical Systems, Los Alamos National Laboratory Report, pp.0-5984, 2000.

C. Barrett, H. B. Hunt, I. , M. V. Marathe, S. S. Ravi et al., Predecessor and Permutation Existence Problems for Sequential Dynamical Systems, Los Alamos National Laboratory Report, pp.1-668, 2001.
URL : https://hal.archives-ouvertes.fr/hal-01183322

C. Barrett, H. B. Hunt, I. , M. V. Marathe, S. S. Ravi et al., Reachability problems for sequential dynamical systems with threshold functions, Theoretical Computer Science, vol.295, issue.1-3, pp.41-64, 2003.
DOI : 10.1016/S0304-3975(02)00395-X

C. L. Barrett, H. B. Hunt, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz et al., Gardens of Eden and Fixed Points in Sequential Dynamical Systems, Discrete Mathematics and Theoretical Computer Science (DMTCS), spec Proc. AA DM?CCG, pp.95-110, 2001.
URL : https://hal.archives-ouvertes.fr/hal-01182974

C. Barrett, H. Mortveit, and C. Reidys, Elements of a theory of simulation II: sequential dynamical systems, Applied Mathematics and Computation, vol.107, issue.2-3, pp.2-3, 2000.
DOI : 10.1016/S0096-3003(98)10114-5

C. Barrett, H. Mortveit, and C. Reidys, Elements of a theory of simulation III: equivalence of SDS, Applied Mathematics and Computation, vol.122, issue.3, pp.325-340, 2001.
DOI : 10.1016/S0096-3003(00)00042-4

C. Barrett and C. Reidys, Elements of a theory of computer simulation I: Sequential CA over random graphs, Applied Mathematics and Computation, vol.98, issue.2-3, pp.241-259, 1999.
DOI : 10.1016/S0096-3003(97)10166-7

R. Beckman, TRANSIMS ? Release 1.0 ? The Dallas-Forth Worth case study, 1999.

B. Durand, Inversion of 2D cellular automata: some complexity results, Theoretical Computer Science, vol.134, issue.2, pp.387-401, 1994.
DOI : 10.1016/0304-3975(94)90244-5

B. Durand, A Random NP-complete problem for inversion of 2D cellular automata, Theoretical Computer Science, vol.148, issue.1, pp.19-32, 1995.
DOI : 10.1016/0304-3975(94)00293-R

B. Durand, Global properties of 2D cellular automata, Cellular Automata and Complex Systems, 1998.

C. Dyer, One-way bounded cellular automata, Information and Control, vol.44, issue.3, pp.54-69, 1980.
DOI : 10.1016/S0019-9958(80)90164-3

P. Floreen and P. Orponen, On the Computational Complexity of Analyzing Hopfield Nets, Complex Systems, vol.3, pp.577-587, 1989.

P. Floreen and P. Orponen, Attraction Radii in Binary Hopfield Nets are Hard to Compute, Neural Computation, vol.3, issue.5, pp.812-821, 1993.
DOI : 10.1073/pnas.79.8.2554

P. Floreen and P. Orponen, Complexity Issues in Discrete Hopfield Networks, Neuro?COLT Technical Report Series, pp.94-103, 1994.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPcompleteness, 1979.

M. Garzon, Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks, 1995.
DOI : 10.1007/978-3-642-77905-3

E. Goles and S. Martinez, Neural and Automata Networks: Dynamical Behavior and Applications, Mathematics and Its Applications series, 1990.
DOI : 10.1007/978-94-009-0529-0

F. Green, NP-Complete Problems in Cellular Automata, Complex Systems, vol.1, issue.3, pp.453-474, 1987.

J. J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proc. National Academy of Sciences (USA), pp.2554-2558, 1982.

J. J. Hopfield and D. W. Tank, Neural computation of decisions in optimization problems, Biological Cybernetics, vol.52, pp.141-152, 1985.

B. Huberman and N. Glance, Evolutionary games and computer simulations., Proc. National Academy of Sciences (USA), pp.7716-7718, 1993.
DOI : 10.1073/pnas.90.16.7716

H. B. Hunt, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns, The Complexity of Planar Counting Problems, SIAM Journal on Computing, vol.27, issue.4, pp.1142-1167, 1998.
DOI : 10.1137/S0097539793304601

L. P. Hurd, On Invertible cellular automata, Complex Systems, vol.1, issue.1, pp.69-80, 1987.

T. E. Ingerson and R. L. Buvel, Structure in asynchronous cellular automata, Physica D: Nonlinear Phenomena, vol.10, issue.1-2, pp.59-68, 1984.
DOI : 10.1016/0167-2789(84)90249-5

M. Jerrum, Two-dimensional monomer-dimer systems are computationally intractable, Journal of Statistical Physics, vol.8, issue.1-2, pp.121-134, 1987.
DOI : 10.1007/BF01010403

M. Jerrum and A. Sinclair, Approximating the Permanent, SIAM Journal on Computing, vol.18, issue.6, pp.1149-1178, 1989.
DOI : 10.1137/0218077

M. Jerrum and A. Sinclair, Polynomial-Time Approximation Algorithms for the Ising Model, SIAM Journal on Computing, vol.22, issue.5, pp.1087-1116, 1993.
DOI : 10.1137/0222066

J. Kari, Reversibility and surjectivity problems of cellular automata, Journal of Computer and System Sciences, vol.48, issue.1, pp.149-182, 1994.
DOI : 10.1016/S0022-0000(05)80025-X

R. Karp and M. Luby, Monte-Carlo algorithms for enumeration and reliability problems, 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pp.56-64, 1983.
DOI : 10.1109/SFCS.1983.35

R. Karp and M. Luby, Monte-Carlo algorithms for the planar multiterminal network reliability problem, Journal of Complexity, vol.1, issue.1, pp.45-64, 1985.
DOI : 10.1016/0885-064X(85)90021-4

S. A. Kauffman, Metabolic stability and epigenesis in randomly constructed genetic nets, Journal of Theoretical Biology, vol.22, issue.3, pp.437-467, 1969.
DOI : 10.1016/0022-5193(69)90015-0

S. A. Kauffman, Emergent properties in random complex automata, Physica D: Nonlinear Phenomena, vol.10, issue.1-2, pp.145-156, 1984.
DOI : 10.1016/0167-2789(84)90257-4

R. Laubenbacher and B. Pareigis, Finite Dynamical Systems, 2000.

B. Martin, A Geometrical Hierarchy of Graphs via Cellular Automata, Proc. MFCS'98 Satellite Workshop on Cellular Automata, 1998.

M. Mitchell, Computation in Cellular Automata: A Selected Review, Nonstandard Computation, pp.95-140, 1998.
DOI : 10.1002/3527602968.ch4

H. Mortveit and C. Reidys, Discrete, sequential dynamical systems, Discrete Mathematics, vol.226, issue.1-3, pp.281-295, 2001.
DOI : 10.1016/S0012-365X(00)00115-1

J. Myhill, The converse of Moore???s Garden-of-Eden theorem, Proc. Amer, pp.685-686, 1963.
DOI : 10.1090/S0002-9939-1963-0155764-9

C. Nichitiu and E. Remila, Simulations of Graph Automata, Proc. MFCS'98 Satellite Workshop on Cellular Automata, 1998.

C. Papadimitriou, Computational Complexity, 1994.

D. Richardson, Tessellations with local transformations, Journal of Computer and System Sciences, vol.6, issue.5, pp.373-388, 1972.
DOI : 10.1016/S0022-0000(72)80009-6

C. Robinson, Dynamical systems: stability, symbolic dynamics and chaos, 1999.

. Zs and . Roka, One-way cellular automata on Cayley graphs, Theoretical Computer Science, vol.132, issue.12, pp.259-290, 1994.

D. Roth, On the hardness of approximate reasoning, Artificial Intelligence, vol.82, issue.1-2, pp.273-302, 1996.
DOI : 10.1016/0004-3702(94)00092-1

K. Sutner, De Bruijn graphs and linear cellular automata, Complex Systems, vol.5, issue.1, pp.19-30, 1990.

K. Sutner, On the Computational Complexity of Finite Cellular Automata, Journal of Computer and System Sciences, vol.50, issue.1, pp.87-97, 1995.
DOI : 10.1006/jcss.1995.1009

K. Sutner, Computation theory of cellular automata, Proc. MFCS'98 Satellite Workshop on Cellular Automata, 1998.

C. Schittenkopf, G. Deco, and W. Brauer, Finite automata-models for the investigation of dynamical systems, Information Processing Letters, vol.63, issue.3, pp.137-141, 1997.
DOI : 10.1016/S0020-0190(97)00110-5

P. Tosic, On Counting Fixed Point Configurations in Star Networks Advances in Parallel and Distributed Computational Models Workshop (APDCM'05), Proc. of the 19th IEEE Int'l Parallel & Distributed Processing Symposium, 2005.

P. Tosic, On Complexity of Counting Fixed Point Configurations in Certain Classes of Graph Automata, Electronic Colloquium on Computational Complexity, 2005.

P. Tosic, Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs, Electronic Colloquium on Computational Complexity, 2005.

P. Tosic, Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata, Electronic Colloquium on Computational Complexity, 2006.

P. Tosic, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, International Journal of Foundations of Computer Science, vol.17, issue.05, pp.1179-1203, 2006.
DOI : 10.1142/S0129054106004339

P. Tosic, G. Agha, and A. Workshop, Concurrency vs. sequential interleavings in 1-D threshold cellular automata, 18th International Parallel and Distributed Processing Symposium, 2004. Proceedings., 2004.
DOI : 10.1109/IPDPS.2004.1303188

P. Tosic and G. Agha, Characterizing Configuration Spaces of Simple Threshold Cellular Automata, Proc. of the 6th Int'l Conference on Cellular Automata for Research and Industry (ACRI'04)'s Lecture Notes in Computer Science (LNCS) series, pp.861-870, 2004.
DOI : 10.1007/978-3-540-30479-1_89

P. Tosic and G. Agha, On Computational Complexity of Counting Fixed Points in Symmetric Boolean Graph Automata, Proc. of the 4th Int'l Conference on Unconventional Computation (UC'05)'s Lecture Notes in Computer Science (LNCS) series, pp.191-205, 2005.

P. Tosic and G. Agha, Parallel vs. Sequential Threshold Cellular Automata: Comparison and Contrast, Proc. of the First European Conference on Complex Systems (ECCS'05), paper # 251, 2005.

P. Tosic and G. Agha, On Computational Complexity of Predicting Dynamical Evolution of Large Agent Ensembles, Proc. of the 3rd European Workshop on Multiagent Systems (EUMAS'05), pp.415-426, 2005.

S. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing, vol.31, issue.2, pp.398-427, 2001.
DOI : 10.1137/S0097539797321602

L. Valiant, The complexity of computing the permanent, Theoretical Computer Science, vol.8, issue.2, pp.189-201, 1979.
DOI : 10.1016/0304-3975(79)90044-6

L. Valiant, The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, vol.8, issue.3, pp.410-421, 1979.
DOI : 10.1137/0208032

I. Wegener, The Complexity of Boolean Functions, Teubner Series in Computer Science, 1987.

S. Wolfram, Computation theory of cellular automata, Communications in Mathematical Physics, vol.30, issue.1, 1984.
DOI : 10.1007/BF01217347

S. Wolfram, Twenty Problems in the Theory of Cellular Automata, Physica Scripta, vol.9, pp.170-183, 1985.
DOI : 10.1088/0031-8949/1985/T9/029

S. Wolfram, Theory and applications of cellular automata, World Scientific, 1986.