Analysis Problems for Sequential Dynamical Systems and Communicating State Machines | SpringerLink
Skip to main content
Springer Nature Link
Log in

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines

  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 2001 (MFCS 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2136))

Abstract

Informally, a sequential dynamical system (SDS) consists of an undirected graph where each node v is associated with a state s v and a transition function f v . Given the state value s v and those of the neighbors of v, the function f v computes the next value of s v . The node transition functions are evaluated according to a specified total order. Such a computing device is a mathematical abstraction of a simulation system. We address the complexity of some state reachability problems for SDSs. Our main result is a dichotomy between classes of SDSs for which the state reachability problems are computationally intractable and those for which the problems are efficiently solvable. These results also allow us to obtain stronger lower bounds on the complexity of reachability problems for cellular automata and communicating state machines.

Part of the work was done while the authors were visiting the Basic and Applied Simulation Sciences Group (TSA-2) of the Los Alamos National Laboratory.

The work is supported by the Department of Energy under Contract W-7405-ENG-36

Supported by a grant from Los Alamos National Laboratory and by NSF Grant CCR-97-34936

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. R. Alur, S. Kannan, and M. Yannakakis. Communicating hierarchical state machines. Proc. 26th International Colloquium on Automata, Languages and Programming (ICALP’99), Springer Verlag, 1999.

    Google Scholar 

  2. S. Arora, Y. Rabani and U. Vazirani. Simulating quadratic dynamical systems is PSPACE-complete. Proc. 26th Annual ACM Symposium on the Theory of Computing (STOC’94), Montreal, Canada, May 1994, pp. 459–467.

    Google Scholar 

  3. C. Barrett, B. Bush, S. Kopp, H. Mortveit and C. Reidys. Sequential Dynamical Systems and Applications to Simulations. Technical Report, Los Alamos National Laboratory, Sept. 1999.

    Google Scholar 

  4. J. Bruck and J. Goodman. A generalized convergence theorem for neural networks. IEEE Trans. on Information Theory, Vol. 34, 1988, pp. 1089–1092.

    Article  MathSciNet  Google Scholar 

  5. C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns and P. Tosic. Gardens of Eden and fixed points in sequential dynamical systems. To appear in Proc. of the International Conference on Discrete Models-Combinatorics, Computation and Geometry (DM-CCG), Paris, July 2001.

    Google Scholar 

  6. C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz and R. Stearns. Predecessor and permutation existence problems for sequential dynamical systems. Under preparation, May 2001.

    Google Scholar 

  7. C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz and R. Stearns. Elements of a theory of computer simulation V: computational complexity and universality. Under preparation, May 2001.

    Google Scholar 

  8. C. Barrett, H. Mortveit and C. Reidys. Elements of a theory of simulation II: sequential dynamical systems. Applied Mathematics and Computation, 1999, vol 107/2-3, pp. 121–136.

    MathSciNet  Google Scholar 

  9. C. Barrett, H. Mortveit and C. Reidys. Elements of a theory of computer simulation III: equivalence of SDS. to appear in Applied Mathematics and Computation, 2000.

    Google Scholar 

  10. S. Buss, C. Papadimitriou and J. Tsitsiklis. On the predictability of coupled automata: an allegory about chaos. Complex Systems, 1(5), pp. 525–539, 1991.

    MathSciNet  Google Scholar 

  11. C. Barrett and C. Reidys. Elements of a theory of computer simulation I: sequential CA over random graphs. Applied Mathematics and Computation, Vol. 98, pp. 241–259, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  12. C. Barrett, M. Wolinsky and M. Olesen. Emergent local control properties in particle hopping traffic simulations. Proc. Traffic and Granular Flow, Julich, Germany, 1995.

    Google Scholar 

  13. P. Floréen and P. Orponen. Complexity issues in discrete Hopfield networks. The Computational and Learning Complexity of Neural Networks: Advanced Topics. Ian Parberry (Editor), 2000.

    Google Scholar 

  14. E. Goles F. Fogelman and D. Pellegrin. Decreasing energy functions as a tool for studying threshold networks. Discrete Applied Mathematics, vol. 12, 1985, pp. 261–277.

    Article  MATH  MathSciNet  Google Scholar 

  15. F. Green. NP-complete problems in cellular automata. Complex Systems, 1(3), pp. 453–474, 1987.

    MATH  MathSciNet  Google Scholar 

  16. H. Gutowitz, Ed. Cellular Automata: Theory and Experiment. North Holland, 1989.

    Google Scholar 

  17. H. Hunt III. On the Time and Tape Complexity of Languages. Ph.D. Thesis, Cornell University, Ithaca, NY, 1973.

    Google Scholar 

  18. Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill Book Company, New York, 1970.

    MATH  Google Scholar 

  19. R. Laubenbacher and B. Pareigis. Finite Dynamical Systems. Technical report, Department of Mathematical Sciences, New Mexico State University, Las Cruces.

    Google Scholar 

  20. C. Moore. Unpredictability and undecidability in dynamical systems. Physical Review Letters, 64(20), pp. 2354–2357, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  21. C. Moore. Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity, 4, pp. 199–230, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  22. H. Mortveit and C. Reidys. Discrete sequential dynamical systems. Discrete Mathematics. Accepted for publication, 2000.

    Google Scholar 

  23. A. Rabinovich. Checking equivalences between concurrent systems of finite state processes. International Colloquium on Automata Programming and languages (ICALP’92), LNCS Vol. 623, Springer, 1992, pp. 696–707.

    Google Scholar 

  24. C. Reidys. On acyclic orientations and SDS. Advances in Applied Mathematics, to appear.

    Google Scholar 

  25. C. Reidys. Sequential dynamical systems: phase space properties. Advances in Applied Mathematics, to appear.

    Google Scholar 

  26. D. Rosenkrantz and H. Hunt III. The complexity of processing hierarchical specifications. SI AM Journal on Computing, 22(3), pp. 627–649, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  27. S. Shukla, H. Hunt III, D. Rosenkrantz and R. Stearns. On the Complexity of Relational Problems for Finite State Processes. Proc. International Colloquium on Automata, Languages and Programming (ICALP’96), pp. 466–477.

    Google Scholar 

  28. K. Sutner. Classifying circular cellular automata. Physica D, 45(1-3), pp. 386–395, 1989.

    Article  MathSciNet  Google Scholar 

  29. K. Sutner. De Bruijn graphs and linear cellular automata. Complex Systems, 5(1), pp. 19–30, 1990.

    MathSciNet  Google Scholar 

  30. K. Sutner. On the computational complexity of finite cellular automata. Journal of Computer and System Sciences, 50(1), pp. 87–97, February 1995.

    Google Scholar 

  31. R. van Glabbeek. The linear time-branching time spectrum. Technical Report CS-R9029, Computer Science Department, CWI, Centre for Mathematics and Computer Science, Netherlands, 1990.

    Google Scholar 

  32. R. van Glabbeek. The linear time-branching time spectrum II (the semantics of sequential systems with silent moves). LNCS 715, 1993.

    Google Scholar 

  33. S. Wolfram, Ed. Theory and applications of cellular automata. World Scientific, 1987.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Los Alamos National Laboratory MS M997, P.O. Box 1663, Los Alamos, NM, 87545

    Chris Barrett, Harry B. Hunt III, Madhav V. Marathe & S. S. Ravi

  2. Department of Computer Science, University at Albany - SUNY, Albany, NY, 12222

    Harry B. Hunt III, S. S. Ravi, Daniel J. Rosenkrantz & Richard E. Stearns

Authors
  1. Chris Barrett
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Harry B. Hunt III
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Madhav V. Marathe
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S. S. Ravi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Daniel J. Rosenkrantz
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Richard E. Stearns
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Mathematical Institute, AS CR, Žitná 25, 115 67, Praha 1, Czech Republic

    Jiří Sgall

  2. Faculty of Mathematics and Physics Institute for Theoretical Computer Science (ITI), Charles University, Malostranské náměstí 25, 118 00, Praha 1, Czech Republic

    Aleš Pultr  & Petr Kolman  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Barrett, C., Hunt, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E. (2001). Analysis Problems for Sequential Dynamical Systems and Communicating State Machines. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_15

Download citation

  • DOI: https://doi.org/10.1007/3-540-44683-4_15

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42496-3

  • Online ISBN: 978-3-540-44683-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics