Complexity
Complexity
 The term complexity has many different meanings. At least
one adjective is needed to help distinguish between different uses of the word.
 Increasing Complexity
 This paper describes and classifies several measures and models of compexity, recounts previous attempts at increasing complexity in artificial ecologies, and offers some suggestions for future studies into artificial complexity.
Structural Complexity
 Abstract: attempt to understand and to measure the notion of complex structure in networks.
 Authors: Anastasiadis, Costa, Gonzales, Honey, Szeliga, Terhesiu.
 2005
 Abstract: In this paper, an objetive and quantitative methodology for developing a stand scales index of structural complexity is demosnstrate.
 Authors: McElhinny , Gibbons, Brack.
 2006
 Abstract: A new complexity measure for graphs and networks is proposed. The central idea of OdC is to apply an entropy measure to the degree correlation matrix, after summation over the offdiagonals. This allows for a quantitative,yet still approximative, measure of complexity. OdC roughly is ‘hierarchysensitive’ and has the main advantage of being computationally not costly.
 Author: Clausten.
 2004
 Abstract: The present paper tries to clarify the growth of complexity during evolution by analysing the concept of
complexity as a combination of variety and dependency.  Author: Heylighen .
 1999
 Abstract: To analyze the evolutionary emergence of structural complexity in physical processes we introduce
a general, but tractable, model of objects that interact to produce new objects. Since the objects have well defined structural properties, we demonstrate that complexity in the resulting population dynamical system emerges on several distinct organizational scales during evolution sustaining interaction.  Authors: Crutchfield , Gornerup .
 2004
 Abstract: Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedurefor finding them. They show that the causalstaterepresentationan Epsilonmachineis the minimal one consistentwith accurate prediction.
 Authors: Shalizi, Crutchfield
 2001
 When Evolution is Revolution. Origins of Innovation
 Abstract: A pictorial tour of the theories of epochal evolution and structural complexity is presented with a view toward the dynamical origins,stabilization, and content of evolutionary innovations.
 Author: Crutchfield
 2001
 Abstract:we propose to use the average atom density (AAD) and the average atom scale (AAS) to evaluate the structural complexity of neural signals.
 Authors: Tong, Thakor, Hopkins
 2005
 Measuring structural complexity for Class Diagrams: An Information Theory Approach
 Abstract: this paper presents a structural complexity model called weightedclass dependence graph (WCDG).
 Authors: Zhou, Xu
 2005
 Abstract: We show that the rate of increase in thermodynamic depth, or dive, is the system’s reversetime Shannon entropy rate, and so depth only measures degrees of macroscopic randomness,not structure. To fix this, we redefine the depth in terms of the causal state representation—emachines—and show that this representation gives the minimum dive consistent with accurate prediction.
 Authors: Crutchfield, Shalizi
 1999
 Abstract: The central thesis of this work is that concepts, techniques, and ideas related to pseudorandomness and quasirandomness should find significant applications in the field of structural complexity theory.
 Author: Sivakumar
 1996
 On the Structure of Valiant’s Complexity Classes
 Abstract: Valiant developed an algebraic analogue of the theory of NPcompleteness for computations of polynomials over a field. They further develop this theory in the spirit of structural complexity and obtain analogues ofwellknown results by Baker, Gill, and Solovay, Ladner, and Schöning.
 Author: Bürgisser
 1999
 Abstract: They introduce a technique of aritmetization of the process of computation in order to obtain novel characterizations of certain complexity classes via multivariate polynomials.
 Authors: Babai, Fortnow.
 1991
 Abstract:
 Authors: McCabe
 1976
 Abstract:present a complexity measure for studying
the structural complexity of multiagent robot formations.  Authors: Muhammad, Egerstedt
 Abstract: propose a measure of structural complexity for binary strings based on the amount of change incorporated in a string.
 Authors: Aksentijevic, Gibson
 2003
 Abstract: studied complexity of the stock market by modeling epsilonmachine of Standardand Poor’s 500 index from February 1983 to April 2006 using causalstate splittingreconstruction algorithm.
 Authors: Park, Won Lee, Yang, Jo, Moon.
Links
 Structural Complexity Laboratory
 The Structural Complexity Laboratory aims to develop, extend and apply automated methods for dealing with problems whose complexity is unknown.
 This site constains proposed contributions to a Special Issue of the Journal COMPLEXITY in which researchers across the sciences are invited to reflect on the role of nerworks and nerwork dynamics in their primary research areas.
 2002
Complexity of sequences:
 Deterministic Complexity and Entropy
 Abstract: Lempel and Ziv (1976) proposed a computable string productioncomplexity. In this
paper, their emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. The linearized measure enables them to propose an entropy measure, observed elsewhere to correspond closely with the KolmogorovSinai entropy in simpledynamical systems.  Authors: Titchener, Nicolescu, Staiger, Gulliver, Speidel.
 2005
 Abstract: A new approach to the problem of evaluatinf the complexity of finite sequences is presented. the proposed complexity measure is related to the numver of steps in a selfdelimitinf production process by which a given sequence is presumed to be generated.
 Authors: Lempel, Zip
 1976
 Abstract: They use to measure the complexity of finite strings, in terms of the number of steps required to recursively constructthe string from its alphabet.
 Author: Titchener
 2000
 Abstract: We provide a proof that the expected length of the shortest feedback register to generate a sequence of length n is less than 2 log p n+ o(1), and also give several other statistics of interest for distinguishing random strings.
 Authors: O'Connor, Snider.
Graph theory
 Abstract: An operation of concatenation is introduced for graphs.
 Authors: Vereijken , Engelfriet
 1994
Graph complexity
The complexity of a graph has been measured in several different ways:
 The number of boolean operations, based on a predetermined set of bolean operators (usually union and interseccion) necessary set of graphs:
 Author:Jukna
 2004
 Author:Lokam
 1998
 Author: Lokam
 2003

The linear complexity of any one of the graph's adjacency matrixs:
 The number of its spanning trees:
 Graph complexity and the Laplacian matrix in blocked experiments, Linear and Multilinear Álgebra.
 Author: Constantine
 1990
 Parametrer for the complexity of finite directed graphs which measures to what extent the cycles of the graph are intertwined:
Graph rewriting
Fitness Landscapes
 Abstract: connections of landscape theory with algebraic combinatorics and random graph theory.
 Authors: Reidys, Stadler
 2002
 Abstract: apply random graph theory to perform the mapping of RNAmolecules to secondary structures which is a good example to study principles of evolucionary optimization.
 Authors: Kopp, Reidys, Schuster .
 1996
 Abstract: techniques based on evolvability statistics of the fitness landscape surrounding sampled solutions.
 Abstract: method for approximating a fitness landscape as a superposition of “elementary” landscapes.
 Authors: Happel, Stadler
 1996
 Abstract: The Travelling Salesman Problem and NKp Fitness Landscapes.
Evolution
 Author: Wright
 1889
 Abstract: htmlified version of Charles Darwin's "The Origin of Species"
 1859
Links
 People, research, writings.
 Conferences, journals.
 GRACO 2005
 Is an international forum for researchers in all areas of combinatorics, graphs and algorithms.
 is a collection of links to home pages of graph theorists.
 The Structural Complexity Laboratory aims to develop, extend and apply automated methods for dealing with problems whose complexity is unknown
 why do we study the complexity of the evolution?
 In Spanish