A comparative classification of complexity measures: Unterschied zwischen den Versionen

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche
(Die Seite wurde neu angelegt: „== Referenz == Wackerbauer, R., Witt, A., Atmanspacher, H., Kurths, J., Scheingraber, H.: A comparative classification of complexity measures. Chaos, Soli…“)
 
 
Zeile 6: Zeile 6:
  
 
== Abstract ==
 
== Abstract ==
−
A  
+
A number of different measures of complexity have been described, discussed, and applied to the logistic map. A classification of these measures has been proposed, dis- tinguishing homogeneous and generating partitions in phase space as well as structural and dynamical elements of the considered measure. The specific capabilities of particular measures to detect particular types of behavior of dynamical systems have been investi-gated and compared with each other.  
−
number  
+
 
−
of  
 
−
different  
 
−
measures  
 
−
of  
 
−
complexity  
 
−
have  
 
−
been  
 
−
described,  
 
−
discussed,  
 
−
and  
 
−
applied  
 
−
to  
 
−
the  
 
−
logistic  
 
−
map.  
 
−
A  
 
−
classification  
 
−
of  
 
−
these  
 
−
measures  
 
−
has  
 
−
been  
 
−
proposed,  
 
−
dis-  
 
−
tinguishing  
 
−
homogeneous  
 
−
and  
 
−
generating  
 
−
partitions  
 
−
in  
 
−
phase  
 
−
space  
 
−
as  
 
−
well  
 
−
as  
 
−
structural  
 
−
and  
 
−
dynamical  
 
−
elements  
 
−
of  
 
−
the  
 
−
considered  
 
−
measure.  
 
−
The  
 
−
specific  
 
−
capabilities  
 
−
of  
 
−
particular  
 
−
measures  
 
−
to  
 
−
detect  
 
−
particular  
 
−
types  
 
−
of  
 
−
behavior  
 
−
of  
 
−
dynamical  
 
−
systems  
 
−
have  
 
−
been  
 
−
investi-  
 
−
gated  
 
−
and  
 
−
compared  
 
−
with  
 
−
each  
 
−
other.  
 
 
== Extended Abstract ==
 
== Extended Abstract ==
  
Zeile 92: Zeile 25:
  
 
== Used References ==  
 
== Used References ==  
 +
[1] P. Graasberger, Toward a quantitative theory of self-generated complexity, Int. 3". Theor. Phys. 25, 907-938 (1986),
 +
How to measure self-generated complexity, Physiea 140 A, 319-325 (1986)
 +
 +
[2] A.N. Kolmogorov, Three approaches to the quantitative definition of information, Inf. Trans. 1, 3-11 (1965)
 +
 +
[3] G. Chaitin, Algorithmic information theory, Cambridge University Press, Cambridge (1987)
 +
 +
[4] P. Grassberger, Problems in quantifying self-generated complexity, Heir. Phys. Aeta 62,489-511 (1989)
 +
 +
[5] K. Lindgren, M. Nordahl, Complexity measures and cellular atomata, Complez Systems 2, 409-440 (1988)
 +
 +
[6] J.E. ttopcroft, J.D. Ullman, Introduction to automata theory, languages and computations, Addison-Wesley, Reading,
 +
Ma., (1979)
 +
 +
[7] A. Lempel, J. Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory 22, 75-88 (1976), Compression
 +
of individual sequences via variable-rate coding, IEEE Trans. Inform. Theory 24, 530-536 (1978)
 +
 +
[8] J. Rissanen, Universal coding, information, prediction and estimation, IEEE Trans. Inform. Theory 30,629-636 (1984)
 +
 +
[9] J. Rissanen, Stochastic complexity and modelling, Annals of Statistics 14, 1080 (1986)
 +
 +
[10] S. Wolfram, Origins of randomness in physical systems, Phys. Rev. Left. 55, 449-452 (1985)
 +
 +
[11] A.C. Yao, Theory and applications of trapdoor functions, Proceedings of the 23rd IEEE Symposium on the Foundations
 +
of Computer Science, 82-91 (1982)
 +
 +
[12] C.H. Bennett, Dissipation, information, computational complexity, and the definition of organization, in Emerging
 +
Syntheses in Science, Ed.: D. Pines, Addison-Wesley, Reading, Ma., 215-233 (1985)
 +
 +
[13] C.H. Bennett, On the nature and origin of complexity in discrete homogeneous, locally-interacting systems, Found.
 +
Phys. 16,585-592 (1986)
 +
 +
[14] H. Koppel, H. Atlan, Program-length complexity, sophistication, and induction, Inform. Sci. 56, 23-33 (1991)
 +
 +
[15] S. Lloyd, H. Pagels, Complexity as thermodynamic depth, Ann. Phys. (N. Y.} 188, 186-213 (1988)
 +
 +
[16] J.P. Crutchfield, K. Young, Inferring statistical complexity, Phys. Rev. Left. 63, 105-108 (1989),
 +
Computation at the onset of chaos, in Complexity, entropy, and the physics of information, Ed.: W. Zurek, Addison-
 +
Wesley, Reading, Ma., 223-269 (1989), J.P. Crutchfietd, Inferring the dynamic, quantifying physical complexity, in Measures of complezity and chaos, Eds.:
 +
N. Abraham et al., Plenum Press, New York, 327-338 (1989)
 +
 +
[17] C.G. Langton, Computation at the edge of chaos: phase transitions and emergent computation, Physica 42 D, 12-37
 +
(1990)
 +
 +
[18] B.A. Huberman, T. Hogg, , Complexity and adaptation, Physica 22 D, 376-384 (1986)
 +
 +
[19] J.E. Bates, H.K. Shepard, Information fluctuation as a measure of complexity, University of New Hampshire, Durham,
 +
preprint (1991)
 +
 +
[20] H. Atmanspacher, Complementarity of structure and dynamics, in Information dynamics, Ed.: H. Atmanspacher.
 +
H. Scheingraber, Plenum Press, New York, 205-220 (1991)
 +
 +
[21] H. Atmanspacher, E. Weinberger, Dualities, context, and meaning, in Information dynamics, Ed.: H. Atmanspacher.
 +
H. Scheingraber, Plenum Press, New York, 343-348 (1991)
 +
 +
[22] J. Guckenheimer, P. Holmes, Nonlinear oscillations, dynamical systems and bifurcation of vector fields, Springer, New
 +
York (1983)
 +
 +
[23] It. Wackerbaner, G. Mayer-Kress, A. Hiibler, Algebraic calculation of stroboscopic maps of ordinary, nonlinear differential
 +
equations, Physica 60 D, 335-357 (1992)
 +
 +
[24] V.M. Alekseev, M.V. Yakobson, Symbolic dynamics and hyperbolic dynamic systems, Phys. Rep. 75, 28%325 (1981)
 +
 +
[25] R.W. Leven, B.P. Koch, B. Pompe, Chaos in dissipativen Systemen, Akademie-Verlag, Berlin (1989)
 +
 +
[26] E.A. Jackson, Perspectives of nonlinear dynamics, vol.g, Cambridge University Press, Cambridge (1990)
 +
 +
[27] G. Nicolis, C. Nicolis, Master-equation approach to deterministic chaos, Phys. Rev. 38 A, 427-433 (1988).
 +
 +
For another definition of doubly stochastic matrices see D.P~. Cox, H.D. Miller, The theory of stochastic processes,
 +
Chapman and Hall, London (1987)
 +
 +
[28] F. Kaspar, H.G. Schuster, Easily calculable measure for the complexity of spatiotemporal patterns, Phys. Rev. 36 A,
 +
842-848 (1987)
 +
 +
[29] C.E. Shannon, W. Weaver, The mathematical theory o/communication, Univ. of Illinois Press, Urbana (1949)
 +
 +
[30] J. Balatoni, A. Renyi, in Selected Papers erA. Renyi, vol.1, Akademial, Budapest, 558 (1976)
 +
 +
[31] P. Grassberger, Generalized dimensions of strange attractors, Phys. £ett. 97 A, 227-230 (1983)
 +
 +
[32] H.G.E. Hentschel, I. Procaeeia, The infinite number of generalized dimensions of fraetals and strange attractors,
 +
Physica 8 D, 435-444 (1983)
 +
 +
[33] P. Grassberger, I. Proeaeeia, Estimating the Kolmogorov entropy from a chaotic signal, Phys. Rev. 28 A, 2591-2593
 +
(1983)
 +
 +
[34] R.S. Shaw, Strange attractors, chaotic behavior, and information flow, Z. Naturforsehung 36 A, 80-112 (1981)
 +
 +
[35] H. Atmanspaeher and H. Scheingraber, A fundamental link between system theory and statistical mechanics., Found.
 +
Phys. 17, 939-963 (1987)
 +
 +
[36] T.C. Halsey, M.H. Jensen, L.P. Kadanoff, I. Procaccia, B.I. Shralman, Fractal measures and their singularities: the
 +
characterization of strange sets, Phys. Rev. 33 A, 1141-1151 (1986)
 +
 +
[37] P. Szdpfalusy, T. Tdl, A. Csod~s, Z. Kov~Lcs, Phase transitions associated with dynamical properties of chaotic systems,
 +
Phys. Rev. 36 A, 3525-3528 (1987)
 +
 +
[38] J.P. Crutchfield, N.H. Packard, Symbolic dynamics of one-dimensional maps: entropies, finite precision, and noise, lnt.
 +
J. Theor. Phys. 21,433-466 (1982)
 +
 +
[39] W. Ebeling, G. Nicolis, Word frequency and entropy of symbolic sequences: a dynamical perspective, Chaos, Solitons
 +
~J Fractals 2, 635-650 (1992)
  
 +
[40] H. Haken, Information and self-organisation, Springer, Berlin (1988
  
 
== Links ==  
 
== Links ==  

Aktuelle Version vom 11. Juni 2016, 17:34 Uhr

Referenz

Wackerbauer, R., Witt, A., Atmanspacher, H., Kurths, J., Scheingraber, H.: A comparative classification of complexity measures. Chaos, Solitons & Fractals 4(1), 133–173 (1994)

DOI

http://dx.doi.org/10.1016/0960-0779(94)90023-X

Abstract

A number of different measures of complexity have been described, discussed, and applied to the logistic map. A classification of these measures has been proposed, dis- tinguishing homogeneous and generating partitions in phase space as well as structural and dynamical elements of the considered measure. The specific capabilities of particular measures to detect particular types of behavior of dynamical systems have been investi-gated and compared with each other.

Extended Abstract

Bibtex

@article{
author = {Wackerbauer, R., Witt, A., Atmanspacher, H., Kurths, J., Scheingraber, H.},
title = {A comparative classification of complexity measures},
journal = {Chaos, Solitons & Fractals},
volume = {4},
number = {1},
pages = {133–173},
year = {1994},
doi = {10.1016/0960-0779(94)90023-X},
URL = {http://dx.doi.org/10.1016/0960-0779(94)90023-X http://de.evo-art.org/index.php?title=A_comparative_classification_of_complexity_measures },
language={English}
}

Used References

[1] P. Graasberger, Toward a quantitative theory of self-generated complexity, Int. 3". Theor. Phys. 25, 907-938 (1986), How to measure self-generated complexity, Physiea 140 A, 319-325 (1986)

[2] A.N. Kolmogorov, Three approaches to the quantitative definition of information, Inf. Trans. 1, 3-11 (1965)

[3] G. Chaitin, Algorithmic information theory, Cambridge University Press, Cambridge (1987)

[4] P. Grassberger, Problems in quantifying self-generated complexity, Heir. Phys. Aeta 62,489-511 (1989)

[5] K. Lindgren, M. Nordahl, Complexity measures and cellular atomata, Complez Systems 2, 409-440 (1988)

[6] J.E. ttopcroft, J.D. Ullman, Introduction to automata theory, languages and computations, Addison-Wesley, Reading, Ma., (1979)

[7] A. Lempel, J. Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory 22, 75-88 (1976), Compression of individual sequences via variable-rate coding, IEEE Trans. Inform. Theory 24, 530-536 (1978)

[8] J. Rissanen, Universal coding, information, prediction and estimation, IEEE Trans. Inform. Theory 30,629-636 (1984)

[9] J. Rissanen, Stochastic complexity and modelling, Annals of Statistics 14, 1080 (1986)

[10] S. Wolfram, Origins of randomness in physical systems, Phys. Rev. Left. 55, 449-452 (1985)

[11] A.C. Yao, Theory and applications of trapdoor functions, Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science, 82-91 (1982)

[12] C.H. Bennett, Dissipation, information, computational complexity, and the definition of organization, in Emerging Syntheses in Science, Ed.: D. Pines, Addison-Wesley, Reading, Ma., 215-233 (1985)

[13] C.H. Bennett, On the nature and origin of complexity in discrete homogeneous, locally-interacting systems, Found. Phys. 16,585-592 (1986)

[14] H. Koppel, H. Atlan, Program-length complexity, sophistication, and induction, Inform. Sci. 56, 23-33 (1991)

[15] S. Lloyd, H. Pagels, Complexity as thermodynamic depth, Ann. Phys. (N. Y.} 188, 186-213 (1988)

[16] J.P. Crutchfield, K. Young, Inferring statistical complexity, Phys. Rev. Left. 63, 105-108 (1989), Computation at the onset of chaos, in Complexity, entropy, and the physics of information, Ed.: W. Zurek, Addison- Wesley, Reading, Ma., 223-269 (1989), J.P. Crutchfietd, Inferring the dynamic, quantifying physical complexity, in Measures of complezity and chaos, Eds.: N. Abraham et al., Plenum Press, New York, 327-338 (1989)

[17] C.G. Langton, Computation at the edge of chaos: phase transitions and emergent computation, Physica 42 D, 12-37 (1990)

[18] B.A. Huberman, T. Hogg, , Complexity and adaptation, Physica 22 D, 376-384 (1986)

[19] J.E. Bates, H.K. Shepard, Information fluctuation as a measure of complexity, University of New Hampshire, Durham, preprint (1991)

[20] H. Atmanspacher, Complementarity of structure and dynamics, in Information dynamics, Ed.: H. Atmanspacher. H. Scheingraber, Plenum Press, New York, 205-220 (1991)

[21] H. Atmanspacher, E. Weinberger, Dualities, context, and meaning, in Information dynamics, Ed.: H. Atmanspacher. H. Scheingraber, Plenum Press, New York, 343-348 (1991)

[22] J. Guckenheimer, P. Holmes, Nonlinear oscillations, dynamical systems and bifurcation of vector fields, Springer, New York (1983)

[23] It. Wackerbaner, G. Mayer-Kress, A. Hiibler, Algebraic calculation of stroboscopic maps of ordinary, nonlinear differential equations, Physica 60 D, 335-357 (1992)

[24] V.M. Alekseev, M.V. Yakobson, Symbolic dynamics and hyperbolic dynamic systems, Phys. Rep. 75, 28%325 (1981)

[25] R.W. Leven, B.P. Koch, B. Pompe, Chaos in dissipativen Systemen, Akademie-Verlag, Berlin (1989)

[26] E.A. Jackson, Perspectives of nonlinear dynamics, vol.g, Cambridge University Press, Cambridge (1990)

[27] G. Nicolis, C. Nicolis, Master-equation approach to deterministic chaos, Phys. Rev. 38 A, 427-433 (1988).

For another definition of doubly stochastic matrices see D.P~. Cox, H.D. Miller, The theory of stochastic processes, Chapman and Hall, London (1987)

[28] F. Kaspar, H.G. Schuster, Easily calculable measure for the complexity of spatiotemporal patterns, Phys. Rev. 36 A, 842-848 (1987)

[29] C.E. Shannon, W. Weaver, The mathematical theory o/communication, Univ. of Illinois Press, Urbana (1949)

[30] J. Balatoni, A. Renyi, in Selected Papers erA. Renyi, vol.1, Akademial, Budapest, 558 (1976)

[31] P. Grassberger, Generalized dimensions of strange attractors, Phys. £ett. 97 A, 227-230 (1983)

[32] H.G.E. Hentschel, I. Procaeeia, The infinite number of generalized dimensions of fraetals and strange attractors, Physica 8 D, 435-444 (1983)

[33] P. Grassberger, I. Proeaeeia, Estimating the Kolmogorov entropy from a chaotic signal, Phys. Rev. 28 A, 2591-2593 (1983)

[34] R.S. Shaw, Strange attractors, chaotic behavior, and information flow, Z. Naturforsehung 36 A, 80-112 (1981)

[35] H. Atmanspaeher and H. Scheingraber, A fundamental link between system theory and statistical mechanics., Found. Phys. 17, 939-963 (1987)

[36] T.C. Halsey, M.H. Jensen, L.P. Kadanoff, I. Procaccia, B.I. Shralman, Fractal measures and their singularities: the characterization of strange sets, Phys. Rev. 33 A, 1141-1151 (1986)

[37] P. Szdpfalusy, T. Tdl, A. Csod~s, Z. Kov~Lcs, Phase transitions associated with dynamical properties of chaotic systems, Phys. Rev. 36 A, 3525-3528 (1987)

[38] J.P. Crutchfield, N.H. Packard, Symbolic dynamics of one-dimensional maps: entropies, finite precision, and noise, lnt. J. Theor. Phys. 21,433-466 (1982)

[39] W. Ebeling, G. Nicolis, Word frequency and entropy of symbolic sequences: a dynamical perspective, Chaos, Solitons ~J Fractals 2, 635-650 (1992)

[40] H. Haken, Information and self-organisation, Springer, Berlin (1988

Links

Full Text

internal file


Sonstige Links

Abgerufen von „http://de.evo-art.org/index.php?title=A_comparative_classification_of_complexity_measures&oldid=32540“