Leonid E Grinin

The Star-Galaxy Era of Big History in the Light of Universal Evolutionary Principles

Keywords: Star-Galaxy Era, cosmic phase of Big History, laws of evolution, universal evolutionary principles, Universe, preadaptations, Evolutionary Studies, evolutionary selection, additive

Big History provides a unique opportunity to consider the development of the Universe as a single process. Within Big History studies one can distinguish some common evolutionary laws and principles. However, it is very important to recognize that there are many more such integrating principles, laws, mechanisms and patterns of evolution at all its levels than it is usually supposed. In the meantime, we can find the common traits in development, functioning, and interaction of apparently rather different processes and phenomena of Big History. Of special importance is the point that many principles, patterns, regularities, and rules of evolution, which we tend to find relevant only for the biological and social levels of evolution, may be also applied to the cosmic phase of evolution. The present article attempts (within such a framework for the first time in the Big History framework) at combining Big History potential with the potential of Evolutionary Studies. It does not only analyze the history of the Cosmos. It studies similarities between evolutionary laws, principles, and mechanisms at various levels and phases of Big History. Such an approach opens up some new perspectives for our understanding of evolution and Big History, their driving forces, vectors, and trends; it creates a consolidated field for interdisciplinary research.

Introduction

Big History provides unique opportunities to consider the development of the Universe as a single process, to detect vectors of changes of certain important characteristics of the Universe (such as complexity and energy) at various phases of this development. However, one should note that the Big History studies tend to pay little attention to such an important aspect as the unity of principles, laws, and mechanisms of evolution at all its levels. 1 I believe that combining the Big History potential with evolutionary approaches can 1 Of course, some authors analyze important general evolutionary mechanisms and patterns, which can be seen at all phases of Big History (see, e.g., David Christian's 'Swimming Upstream' and the conclusion of David Baker's 'Shoulders of Giants' in this volume). One can also mention Fred [START_REF] Spier | Big History and the Future of Humanity[END_REF] and David Baker's '10 500 . The Darwinian Algorithm and a Possible Candidate for a "Unifying Theme" of Big History' (2013). However, we should state our position on Baker's general idea in that interesting paper. While also dealing with universal evolutionary principles like ours, Baker innovates by starting his article with analyzing the selection of universes within which open wider horizons in this respect (see Grinin et al. 2011). Indeed, common traits in development, functioning, and interaction can be found in apparently quite different processes and phenomena of Big History. In this respect the universality of evolution is expressed in those real similarities that are detected in many manifestations at all its levels. This article is an attempt to combine Big History potential with the potential of Evolutionary Studies in order to achieve the following goals: 1) to apply the historical narrative principle to the description of the star-galaxy era of the cosmic phase of Big History; 2) to analyze both the cosmic history and similarities and differences between evolutionary laws, principles, and mechanisms at various levels and phases of Big History. As far as I know, nobody has approached this task in systemic way yet. It appears especially important to demonstrate that many evolutionary principles, patterns, regularities, and rules, which we tend to find relevant only for higher levels and main lines of evolution, can be also applied to cosmic evolution. Moreover, almost everything that we know about evolution may be detected in the cosmic history, whereas many of the evolutionary characteristics are already manifested here in a rather clear and salient way. One should also bear in mind that the origin of galaxies, stars, and other 'celestial objects' is the lengthiest evolutionary process among all evolutionary processes in the Universe. Such an approach opens new perspectives for our understanding of evolution and Big History, of their driving forces, vectors, and trends, creating a consolidated field for the multidisciplinary research.

Our world is immensely diverse and unlimited in its manifestations. However, fundamentally it is a single world -that is why it is so important to study those fundamentals.

I. THE FORMATION OF THE LARGE-SCALE STRUCTURE

OF THE UNIVERSE Preconditions. After the Big Bang, our Universe 'lived' for quite a long period of time without any stars, galaxies, clusters, and superclusters of galaxies (Khvan 2008: 302). The formation of modern structure of the Universe lasted for billions of years. However, the first stars and galaxies turn out to have emerged not later than 200-400 million years after the Big Bang. And what was the matter from which they had emerged?

Approximately 270,000 years after the Big Bang, a large phase transition occurred resulting in the emergence of matter in the form of atoms of hydrogen and helium. Later, they started to consolidate in new structures (see below). The main mass of this matter concentrated in gas-dust clouds that could have tremendous sizes (dozens parsecs, or even more). 2 For the first time we observe Nature in the role of a constructor. Before that, it had formed just the basic elements. Now one could observe the emergence of enormous structures from tiny particles and 'specks of dust'. After that one could observe this constantly: large-scale structures are composed of myriads of minute particles and grains.

there could appear some physical laws and parameters allowing the universes to evolve. Baker explores the selection mechanism among an enormous number (potentially 10 500 -a fabulous number even for modern cosmology) of universes in the 'multiverse'. We suppose that his algorithm with respect to the selection of universes could hardly be called properly Darwinian. He rather speaks about the evolutionary selection in general -that is not the selection of the fittest, but rather the selection of those capable to evolve -which is much wider than the Darwinian selection. The idea that such selection is not Darwinian is confirmed if one employs Christian's (this volume) and Smolin's (2008: 34, which Christian refers to) definitions of the Universal Darwinian mechanism. Such mechanism should obviously include a mechanism of reproduction. It is clear that there is not any mechanism of reproduction in the case of isolated universes. However, for a theory of the presence of Darwinian reproduction in the evolution of multiple universes see Smolin's earlier book The Life of the Cosmos (1997). 2 1 parsec ≈ 31 trillion km.

The formation of clouds (and later stars and galaxies) meant a concentration of matter on enormous scale, which could have been caused only by gravity. However, this only force is insufficient for structuring, because in 'an absolutely homogenous universe the emergence of large-scale structures (galaxies and their clusters) is impossible' (Dolgov et al. 1998: 12-13). Thus, certain seed grains are necessary -this is comparable with formation of rain drops that emerge around particles of dust or soot; or with formation of a pearl around grit. Small fluctuations are often needed for the powerful forces to start working. Actually, minor fluctuations (minute deviations from homogeneity) occurred in the Universe early on. Then the larger fluctuations happened. They could act as seed grains for the formation of galaxies and the matter concentrated around them on a much larger scale until the quantity started to transform into a new quality. This is a perfect example of the point that the non-uniformity (in particular with respect to the distribution of matter, energy, etc.) is a universal characteristic. Any major evolutionary shift in biological and social systems is preceded by the concentration of certain forms, resources and conditions in certain niches and places. Thus, in the major system the common processes may proceed in their usual way, whereas in the concentration zone some peculiar processes start (this is what takes place in star formation zones).

Dark and light matter. Nowadays it is generally accepted that dark matter plays an important role in the formation of the first galaxies, as it appeared capable of consolidating into clusters much earlier than the light (baryon) matter. The latter could not contract until the end of the hydrogen recombination (atom formation) due to radiation (270,000 years after the Big Bang). Only when hydrogen nuclei and electrons were able to merge and form atoms, whereas photons separated from the matter and flew away, the pressure of the radiation dramatically dropped. As a result, the light matter would fall in potential holes prepared for it by the dark matter. Though the dark matter was initially more capable to structuring than the light matter, the progress toward structuring turned out to be very short and leading to almost a dead-lock. 3 Meanwhile, the evolutionary potential of the light matter was based on the 'achievements of the dark matter'. Such a model of development is rather typical for evolution. For example, long before the transition to agriculture some gatherers of cereal plants invented many things (sickles, granaries, and grinding stones) that later turned to be rather useful for agriculturalists, whereas specialized huntergatherers turned out to be an evolutionary dead end.

The epoch of formation of the large-scale structure of the Universe. First galaxies and stars. There are rather diverse opinions on timing, process characteristics and sequence of formation of stars, galaxies, galaxy clusters and superclusters. There is a hypothesis that galaxy protoclusters were first to originate. However, a more commonly held hypothesis suggests that protogalaxies (in the form of giant condensed gas clouds) were the first to emerge within the structure of the Universe, and later they became the birthplace for separate stars and other structural elements (see, e.g., [START_REF] Gorbunov | Introduction to the Theory of the Early Uni-verse: Cosmological Perturbations and Inflationary Theory[END_REF].

However, in recent years new evidence has come to hand to support the idea that those were the stars that appeared first. This discovery somehow modified the previous theories. At present, it is widely accepted that the stars were first to emerge, but those were the giant stars, much more massive than most of the later-formed ones [START_REF] May | Bang: The Complete History of the Universe[END_REF]. Because of the absence of carbon, oxygen and other elements that absorb the energy from condensing clouds, the process proceeded more slowly in that epoch; thus, only giant clouds could condense producing massive stars hundreds times larger than the Sun (Ibid.). Such giant stars lived only a few million years (the larger is star, the shorter is its life). In addition, the first stars contained a small amount of heavy elements. Thus, more than one generation of stars could change, until the quantity of heavy elements gradually increased. The emergence of 'heavy elements' from the 'dead star stellar remnants' resembles the formation of fertile soil from the remnants of dead plants. The circulation of matter in the Universe is always observed everywhere and at all levels.

In recent years we have witnessed the discovery of a few galaxies that are claimed to be the oldest in the Universe. Meanwhile, the dates of formation of the first galaxies are shifted closer and closer to the Big Bang. The emergence of the first galaxies is dated to less than 400 million years after the Big Bang; and there are even claims that some more ancient galaxies have been discovered. They are claimed to have emerged only 200 million years after the Big Bang (see European Commission 2011). The evidence on the first stars refers to c. 150-200 million years after the Big Bang -hence, stars and galaxies appear to have emerged almost simultaneously.

II. THE ERA OF THE STAR-GALAXY STRUCTURE OF THE UNIVERSE

The whole history of the star-galaxy phase of cosmic evolution is basically the history of formation of various structures of different size, as well as their merging into larger structures (but it is a history of their disintegration as well).

1. The structure of the Universe 1.1. Some principles describing the basic structure of the Universe may be applied to different levels of evolution (below we will consider just two of them).

1) The combination of antagonistic qualities. For example, in the structure of the Universe one can find the combination of uniformity and non-uniformity. The uniformity is already manifested at the inflation phase, when the Universe started inflating evenly in all dimensions. The uniformity has preserved till present, but only at the largest scale (of an order of magnitude of 100 megaparsecs 3 ). For reference, the size of the largest galaxy clusters (such as our Local Group with the center in the Virgo constellation) is 40 megaparsecs at most [START_REF] Gorbunov | Introduction to the Theory of the Early Uni-verse: Cosmological Perturbations and Inflationary Theory[END_REF]. The non-uniformity of the Universe is manifested at scales smaller than 100 megaparsecs; and the smaller is the scale, the more salient is the unevenness. The combination of antagonistic qualities is a phenomenon that is rather characteristic for many other evolutionary levels.

2) Density and sparsity can be traced everywhere, starting from the atomic structure, where the mass is concentrated in a tiny nucleus, while most of the atom is an empty space. There is a huge non-uniformity between the scale of the Universe and the space that the main mass of the light matter occupies within it. It is concentrated, first of all, in stars which actually occupy only a 10 -25 part of the total volume of the Universe (not taking into account the galaxy nuclei [Pavlov 2011: 43]). Not only the hard matter is distributed very unevenly throughout the Universe; the same is true of the gas. Much of this gas is concentrated in giant molecular clouds which are of many thousands of solar masses (Lipunov 2008: 37). The principles of uneven distribution of the matter mass at different evolutionary levels are rather similar. For example, at present the main mass of the Earth's population is concentrated in a rather small territory in comparison with the total territory where life on the Earth is possible.

The structure of the contemporary Universe

The main structural elements of the Universe are galaxies, their clusters, and superclusters. All the structural elements are rather stable in terms of gravitation, though they can split, merge, and collide. Galaxies are integral structural entities with a rather complex structure which includes, in addition to regions and arms, a nucleus (core), semi-periphery (so called 'disc'), and periphery (so called 'halo') (Baade 2002: 255). The halo consists of both single stars and various stellar clusters. The halo's radius (a few hundred thousand light years) is much larger than the radius of the galaxy's disc. 4According to Hubble, the galaxies are classified into spiral, elliptical, and irregular with various subtypes (Ibid.: 18-32); yet, by now one more galaxy type has been identified -the lenticular galaxies.

A galaxy contains around 100 to 200 billion stars. There are small (dwarf) galaxies with a few million stars, there are also giant galaxies consisting of up to a trillion stars. Our galaxy with its mass of about 10 11 solar masses is one of the largest ones. It contains 200-300 or even more billions of stars. However, the mass of our neighbor -the Great Andromeda Nebula -is about three times larger.

Stars are distributed rather unevenly throughout galaxies, stars are parts of various groups and clusters; some of them consist of just a few stars, but some clusters can contain a few million stars. For example, within our Galaxy more than 1,500 star clusters have been identified [START_REF] Surdin | Stars Production[END_REF]. There are many globular clusters -spherical clusters tightly bound by gravity and consisting of hundreds of thousands, as a rule, rather old stars.

Galaxies are complex and (to a considerable extent) self-regulating systems, within which some stars disintegrate, whereas new stars form from cosmic gas and dust. The circulation (which results in processes of renovation of matter and its mixing) takes place at all levels of the Universe -both spatially and at different levels of evolutional complexity.

An average galaxy cluster consists of 500-1000 galaxies. Galaxy clusters have a rather regular structure which is likely to include a massive nucleus in the center. Galaxy superclusters are entities consisting of 2-20 galaxy clusters and galaxy groups as well as of isolated galaxies. In general, there are known more than 20 superclusters, including our Local Group.

Generations of galaxies and stars

There are rather diverse opinions on the number of generations throughout the evolution of the Universe. In addition, there is no consensus on which galaxies should be regarded as old, and which galaxies should be considered young. The point is that within a single galaxy one can find stars and their aggregates that considerably differ in their type, age, and other parameters. For example, the age of our Milky Way galaxy is more than 12 billion years, but that is the age of just its halo while many stars in its branches are only two-five billion years or less. Yet, it appears possible to single out a few widely accepted basic ideas.

1) In the evolution of the Universe, there have been three (or at least two) generations of galaxies and stars. In general, old galaxies are smaller and dimmer. Their stars contain dozens of times smaller quantities of heavy elements than the Sun. The astronomers can hardly observe any star formation processes within such galaxies. There is also a hypothesis that more dark mass is concentrated in old galaxies in comparison with younger ones. The same way, older and younger stars differ from each other in their size, luminosity, and chemical composition.

2) It is difficult to speak about a clear periodization of generations of galaxies, because of the ongoing process of formation of galaxies and stars. Galaxies need to constantly renew their composition in order to retain their identity. As Joseph Shklovsky maintains, in this respect galaxies are very similar to primary forests with its mix of tree ages (whereas the age of trees is much less than the age of the forest itself [Shklovsky 1984: 45]). The motility and variability of the celestial landscape resembles very much the motility of geological landscapes.

3) The formation of galaxies can proceed in different ways, for example, through the absorption of smaller galaxies by the larger ones. Another way is merging. Galaxies of younger generations can sometimes form through the accretion of a few small, weak and compact galaxies into a single galaxy. In this case they became 'building blocks' for galaxies. Finally, it may happen that two large galaxies collide. Such a collision may take billions of years and be accompanied with active star formation and emergence of very large and bright stars. Finally, galaxies may diverge again, but in this case they turn out to be very different from what they used to be before the collision, whereas one more galaxy may emerge out of the matter estranged from the both galaxies (see May et al. 2008: 142).

There are numerous analogies to those models of galaxy formation in biological, geological, and, especially, social evolution. As stars and galaxies are composed of more or less homogenous matter (that can be divided or united rather easily), they somehow paradoxically resemble societies that consist of people who can be included into other societies through integration or capture. On the other hand, captures are also attested among social animals (e.g., among ants see [START_REF] Genet | Humanity: The Chimpanzees Who would be Ants[END_REF].

4) Galaxies are collections of different types of stars. However, there are certain peculiarities as regards the position of old and young stars within galaxies. Thus, within our galaxy the younger stars (such as the Sun which is a few billion years old) are generally larger, hotter and brighter. They are located toward the disc plane, and, especially, within the galaxy arms; whereas in the galaxy periphery (in its halo) one would find older stars more than 12 billion years old (which suggests the overall age of our galaxy). Yet, older and younger stars may be also located rather close to each other. Thus, one may find many old stars near the galaxy center (bulge), but there are also young stars that emerged from the matter produced by the disintegration of older stars. The highest stellar density is found in the galaxy center where it reaches a few stars per cubic parsec.

On the one hand, the preservation of generations of stars and galaxies demonstrates an additive character of the evolution of abiotic systems, whereas we can see elements of substitutive model of evolution at biological phase and its full system at social phase of Big History. However, the capture of stars and galaxies with their subsequent integration and prolonged processes of collision of galaxies demonstrates that in abiotic natural systems one may still find some other models of evolution -connected with 'wars' and 'submission of outsiders'.

The type of development through the emergence of different generations of individuals and species (preserving certain generic features, on the one hand, and accumulating important changes in their structure and characteristics, on the other) is rather widespread at all phases and levels of universal evolution. Within any biological class or order (e.g., perissodactyls) we can see how important characteristics vary and gradually change from one species to another, whereas due to those characteristics some species press out others and occupy better niches (see, e.g., [START_REF] Grinin | Macroevolution in Wild-life and Society. Moscow: LKI[END_REF]. Various types of states and civilizations also rather vividly illustrate the progress: for example, more organized and developed states emerge through the absorption of the achievements of less developed generations of states, which one can illustrate using examples from the history of Ancient Rome, Byzantium, some Medieval European states and so on. The coexistence of different generations sometimes leads to the situation when younger and more advanced entities either transform the older ones or form a symbiosis with them (though in some places one may find 'restrictions' for older types and generations).

Change of the chemical composition of the Universe

Hydrogen has always been the most abundant element in the Universe chemical composition; yet, its share constantly decreased. This occurred (and occurs) because hydrogen is the main fuel for the nuclear fusion reactions that support life and luminosity of stars. Increasing temperatures inside the core of some stars were needed for the formation of new elements that were absent in the era of recombination. However, all of the fusion reactions that occur to produce elements larger than iron no longer release energy. Reactions of another type are needed for the formation of elements heavier than iron -those reactions consume more energy than release. That is why there are such relatively small amounts of heavy elements in the Universe. Yet, such peculiar reactions do take place -for example, in neutron stars and during explosions of supernovas. When supernovae explode, heavy elements are expelled through the Universe with stellar winds and through the fall of the dispersed matter on the surface of cosmic bodies (so-called accretion). As stars turn to be the main centers of the synthesis of chemical elements, the distribution of heavy elements in the Universe is very inhomogeneous.

The emergence of heavy elements and their concentration in certain bodies and compositions are extremely important processes, which lead to an enormous increase in the number of matter combinations, and consequently have an evolutionary potential; in particular, they lead to the start of the full-scale chemical, biochemical, and biological processes. In certain respects, such a slow and uneven accumulation of new structural elements (heavy elements) resembles the process of an accumulation of valuable mutations in biological evolution, or the accumulation of valuable innovations in social evolution (all of them bring the expansion of the evolutionary potential and increase the rates of evolutionary changes).

The Evolution of Galaxies and Stars

Processes of the formation of galaxies and stars

Until quite recently, the processes of star formation were entirely concealed from an external observer; however, at present due to the technological progress one can observe some aspects of those processes in many parts of our galaxy. Those observations confirm the theory of stellar formation from cold clusters that are heated by gravitation and pressure.

Briefly, this process may be described as follows. Within giant hydrogen and helium clouds, some heterogeneities emerge, which launch (under certain conditions) the gravitation processes that start to collect that mass into spherical forms. Sometimes a direct for-mation of a giant mass of gas clouds takes place, from which a galaxy or a star cluster later emerges. In this case the cloud fragmentation may occur and thus, more and more gascloud spheres (there could be hundreds of millions, or even hundreds of billions of them) emerge, which can gradually transform into protostars. This process continues up to the point when the gas density becomes so high that each new fragment already has a mass of a star (Surkova 2005: 49). Then the gravity starts impeding further fragmentation. This process is denoted as 'cascade fragmentation'. It is remarkable that it resembles certain processes in social evolution -for example, the fragmentation of large early states into separate parts that decentralize up to the point when further division becomes unreasonable (e.g., in certain periods there were dozens and hundreds of independent states in the territories of Germany or France).

As enormous gas/dust clouds appear unstable, they disintegrate into large bundles, so the formation of stars proceeds in groups. This phenomenon is of interest not only with respect to stellar evolution. The group formation is rather typical for evolution in general (in this way populations and sometimes new species emerge; chiefdoms, city-states, and sometimes political parties emerge in groups, and so on).

The further process of the star formation is connected with the point that the initial compression heated the gas to a rather high temperature that, on the one hand, prevents the further compression of the gas, and, on the other hand, eventually contributes to the onset of the nuclear fusion reaction (Hawking 2001: 63-64).

Diversity of stars and galaxies

Diversity is an absolutely required condition of evolutionary development. And this condition is fully realized within cosmic evolution. As has been mentioned above, galaxies differ in their types, age, size, and structure. In particular, a galactic structure is to a large degree determined by the initial conditions of its formation (e.g., by the character of rotation of the original gas clump from which a galaxy is formed). Stars differ in mass, temperature, chemical composition, luminosity, age, and other characteristics. Those differences may vary greatly. For example, with respect to masses, stars range in mass from about 0.1 to 100 or more solar masses. It is rather natural that the number of smaller entities is orders of magnitude larger;5 actually, the same phenomenon may be observed, for example, in Zoology or Political Geography where the number of small animals or countries is much larger than that of large ones.

The life-cycle of a star: Stages of stellar birth, aging, and death

Protostars. As mentioned above, stars emerge through the condensation and compression of gas clouds under the influence of gravitational forces. This is a protostar phase. In comparison with the subsequent life of a star, the period of its slow contraction seems rather short; however, actually this is not a quick process as it continues sometimes up to 50 million years (Surkova 2005: 50). During this period of time, there is a tremendous rise in the temperature at the core of the protostar, the temperature may grow up to 8-10 million Kelvin, and, as a result, thermonuclear reactions become possible. The protostar becomes a young star. However, an external observer will only be able to see it in a few hundred thousand (or even a few million) years when the cocoon of gas and dust surrounding the protostar dissipates.

Actually, we deal with a sort of miracle -a giant shining incandescent body, which is capable of living for billions of years, emerges from an absolutely amorphous, lacking any structure, opaque, and cold mass of gas mist. In other words, we deal here with a vivid example of self-organization that takes place under the influence of gravitation and thermodynamic laws. In particular, an intensive contraction leads to heating, which increases the internal pressure, which, eventually, stops the compression process.

One may also note that the emergence of stars and galaxies must have a certain trigger that creates turbulence and heterogeneity. Those triggers and catalyzers are the inherent components of evolutionary mechanisms that may be found in many processes: in chemical and geological processes, within biological evolution with respect to fast formation of species, or within social evolution with respect to state formation (see Grinin 2011 for more details). The supernova shock wave, the collision of a molecular cloud with spiral arms of a galaxy and other events can become such a trigger of the star formation (Surkova 2005: 50).

Another (the longest) macrophase is the main sequence star. During this phase of the stellar lifetime, nuclear-fusion reactions that burn hydrogen to helium in the core, keep the star shining. That is why the duration of the main sequence phase depends mainly on the stellar mass. The more massive is the star, the shorter its lifespan on the main sequence (as with a larger mass the 'fuel combustion' processes run more intensively). A star preserves its size and form due to the mutual struggle of two forces: the gravity that tries to compress the star and the gas pressure produced as a result of nuclear reactions and powerful heating. There is a dynamic equilibrium between temperature and gas pressure. With growing temperature, the gas expands and works against the gravitation forces, which results in cooling of the star; this way the thermal balance is kept. In the lifetime of stars and galaxies, as well as at all other levels of evolution, we find numerous cases and different forms of the interaction between two opposite processes which make it possible for 'individuals' to live. The processes of assimilation and dissimilation support vital activities within biological organisms; the processes of animal reproduction and their extermination by predators support the population balance; interaction between processes of production and consumption is the basis of the reproduction of social systems, and so on.

Red giants. The new phase of stellar evolution is connected with the exhaustion of hydrogen supplies. The gas pressure (that maintained the star balance when necessary fuel was available) decreases and the stellar core compresses. This leads to a new increase in temperature. A star starts to burn heavier elements and thus, the stellar composition significantly changes. Simultaneously with the compression of the core, the star's outer layers expand. In general, the star inflates and expands a few hundred times, and it transforms into a red giant. This phase lasts for about one tenth of the 'active lifetime' of a star, when the processes of nuclear fusion go on in its depths.

Star death: three cases. The next phase is the transformation of a red giant or supergiant. Actually, the new form depends on stellar mass and a number of other characteristics such as the stellar rotation and velocity, the degree of its magnetization, and so on. following three outcomes are considered most typical. They depend on stellar mass (but the limit value estimates vary significantly, and so below I will mention the main alternative values after the slash). 6 Stars with the masses smaller than 1.2-1.4/3 solar masses transform from red giants into the so-called 'white dwarfs', when the star sheds its outer envelope to form a planetary nebula with an extremely contracted core (down to the size of the Earth). The further compression does not occur because of the so-called degenerate electron gas pressure that does not depend on temperature. As a result, the white dwarf is rather stable. However, due to the lack of hydrogen and helium, thermonuclear fusions can no longer proceed within such a star. A white dwarf is very hot when it is formed; yet, afterwards the star cools and transforms into a 'black dwarf', that is, it becomes a cold dead cosmic body.

For stars with an initial mass of more than 1.2-1.4/3, but less than 2.4-3/7-10 solar masses, their slow and gradual aging results in an 'infarct', that is a collapse. After the depletion of hydrogen and the decrease of the internal gas pressure (that used to balance the gravity), under the influence of gravity the core gets extremely compressed (by dozens thousand times -up to the radius of ten kilometers) just in less than a second. Almost simultaneously the external layers of the star are blown away with a huge speed as a result of shock wave. This supernova shines brighter than millions of ordinary stars, but for a very short period of time. This explosion expels the stellar material into interstellar medium and thus, there occurs the formation of considerable quantities of heavy (heavier than iron) elements that afterwards concentrate in various celestial bodies. The remaining core contracts to become a neutron star. In its size, such a star is 5 billion times smaller than the Sun, but it is hundreds of thousands of times brighter because the temperature on its surface is 1000-1500 times higher than on the Sun (Lipunov 2008: 133).

If stellar mass exceeds the limit of 3/7-10 solar masses, after hydrogen is burnt out it will start collapsing and explode (though sometimes it may collapse without an explosion), but the force of compression will be unlimited, as the gravity becomes enormous because of the huge mass and absence of internal forces that can prevent the collapse. The action of the gravitational force which is balanced by nothing leads to the situation when the stellar diameter becomes infinitesimally small. According to theoretical calculations, the star is transformed into a black hole whose gravity fields are strong for light to escape.

III. UNIVERSAL EVOLUTIONARY PRINCIPLES IN THE STAR-GALAXY ERA

Life, Death, and Catastrophes in the Evolutionary Aspect

The lifetime of stars in terms of maintaining and breaking the dynamic equilibrium First of all, there is a thermal equilibrium, when the rate of energy produced in the core (through thermonuclear fusions) balances the loss of energy through the emission of radiation into space. This equilibrium is broken when hydrogen fuel is gone. The reserves are apparently compensated when a star starts using another type of energy. This may occur through the contraction of the star which begins fusing helium into carbon, thus producing many times more energy for every atom; afterwards heavier elements may be used as fuel, and each heavier element will produce more and more energy per atom. Meanwhile, the core of the star begins to increase in temperature. There is equilibrium in terms of pressure of different forces and preservation of a certain form and size of the star. Within the main sequence phase, the balance is maintained as the gravity pulls all the stellar matter inward, toward the core, while gas pressure pushes heat and light away from the center. This pressure exists until the reserves of nuclear fuel are exhausted (Efremov 2003: 97). With re-spect to red giants one may speak about equilibrium of another kind in two dimensions. In the core the temperature grows due to contraction and thermonuclear reactions of higher levels (described above) start; as a result of those reactions the temperature may grow up to 100 million Kelvin. That is why a stronger gravity is balanced by a stronger (due to temperature) gas pressure. In the meantime, within the shell the equilibrium is achieved through the multifold expansion of the outer layers. In neutron stars and white dwarfs, the subsequent phases of the stellar lifetime, there is their peculiar equilibrium.

The problem of the individual's death. Death as an opportunity for life to go on. Stellar life and death can hardly leave anybody indifferent. Actually, within the Big History framework, this is the first time when we come across the problem of a life cycle of individual objects in such an explicitly expressed form. On the one hand, the star's fate, lifespan, and type of death depend on initial parameters, as if they were 'genetically programmed' (and, hence, they may be forecasted); on the other hand, they may be altered by some contingencies. Thus, the star's fate is not 'fatal', indeed. Binary star systems increase highly the variability of the individual star fates; as Lipunov (2008: 252) puts it, we deal here with a kind of 'quadratic evolution'. What is more, it is actually possible to speak about differences in the 'individual' stellar behavior or 'within a group', because the interaction of two, three, and more stars may lead to very significant differences and unusual results that cannot emerge within the development trajectory of individual stars. In fact, similar patterns are observed at other levels of evolution, when behavior of pairs or groups of individuals produces outcomes radically different from the ones observed with respect to the behavior of an individual not interacting with others.

Finally, the meaning of individual's death for evolution may be different. Up to a certain degree one may observe a direct correlation between the 'strength' of death, the power of the stellar explosion, and the formation of conditions for a new evolutionary search. Stellar explosions affect the dynamics of their environment; consequently, they may help create unusual conditions that contribute to the emergence of certain developmental deviations. Within tens of thousands years the zone of explosion expands to a vast area of interstellar medium (covering the distances of dozens of parsecs); in this area one can see the formation of new physical conditions (in particular, temperature, density of cosmic rays and magnetic fields strength). Such a disturbance enriches the respective zone with cosmic rays and brings changes to chemical composition (Shklovsky 1984: 209). The explosions also contribute to star formation. Thus, a star does not die in vain. One can draw here an interesting analogy with extinctions in biological evolution which contribute to new directions of speciation. The stellar destruction can be also compared with the disintegration of large empires with all the subsequent repercussions. The disintegration of a large empire leads to a cascade of new states forming both in the place of the empire and even beyond its borders. Historical detonation contributes to politogenesis the same way as the cosmic detonation contributes to star formation.

Synthesis of gradualism and catastrophism. With respect to cosmic evolution one may observe a combination of two principles that provoke endless discussions in geology and biology. The subject of those discussions is what principle prevails in evolution. Are we dealing mostly with slow gradual changes, eventually leading to major changes (gradualism)? Or, does the development mostly proceed through sharp revolutionary breakthroughs which in biology are often connected with catastrophes? Within star-galaxy evolution the combination of both principles is more than just evident. Here, as at no other evolutionary level, both modes of evolution are organically combined in individual fates of the stars. The main sequence phase of stellar evolution (when the fusing of hydrogen occurs) demonstrates the gradual character and the importance of slow and prolonged processes. However, catastrophes of various scales can take place within the lifetime of any star. For some stars, such radical changes may manifest in major -but still local -changes (such as shedding the outer layers), whereas for other stars these might be tremendous catastrophes when stars die, figuratively speaking, 'brightly' and 'heroically', illuminating the Universe, leaving a billion-year-long footprint of light. The latter, that is the extraordinary phenomena and events, both among the stars and among humans are less numerous than the former, that is the common ones.

Some Evolutionary Ideas in Connection with the Star-Galaxy Phase of Evolution of the Universe

In the evolutionary process of formation of stars, galaxies, nebulae, and cosmic clouds one can distinguish a number of important evolutionary principles and laws that are not evident. Their detection is important for understanding the unity of principles of development of the Universe. Those principles and observations are grouped below into several blocks.

Evolution proceeds with constant creation and destruction of objects

Nature, when creating, destroying, and renewing various objects, 'tests' many versions, some of which turn out to be more effective and have more chances to succeed in terms of evolution. For such a situation of selection within constant destruction and creation process, it appears possible to apply a rather appropriate notion of creative destruction introduced by Josef [START_REF] Schumpeter | Capitalism, Socialism and Democracy[END_REF].

 'Evolution is stronger than individual objects'. Cosmic processes are accompanied by constant emergence, development, change, and death of various objects (stars, galaxies, and so on). Thus, here one can point as relevant the principle that was expressed by Pierre Teilhard de [START_REF] Teilhard De Chardin | The Phenomenon of Man[END_REF] with respect to life in the following way: 'life is stronger than organisms', that is, life goes on exactly because organisms are mortal. The same is relevant to stellar evolution. We may say here that the cosmos is stronger than stars and galaxies; and in general, evolution is stronger than individual objects.

 Rotation and keeping balance take place due to constant destruction (or transition to new phases in the lifecycle) of some objects and the emergence of others. This keeps balance and creates conditions for development, because development is a result of change of generations and species.

 In every end there is a beginning. Star-evolutionary 'relay race'. The material of dead objects becomes building blocks for the formation of new objects. This represents the circulation of matter and energy in nature; on the other hand, this represents a sort of 'relay race'. 7 The latter allows using the results of long-lasting processes (in particular, the accumulation of heavy elements). 8 Thus, we deal here with the above mentioned 'creative destruction' -the creation of new objects due to the destruction of the old ones, which ensures continuity and provides new forms with space for advancement (e.g., the change of generations of biological organisms always results in certain transformations). The change of rulers may not necessarily lead to radical social changes; however, each new ruler is somehow different from his predecessor, as a result the accumulation of historical experience occurs.

 New generations of organisms and taxa are a mode of qualitative development. One may also detect generations of taxa, which already have significant evolutionary and systemic differences. Thus, generations of stars differ in terms of their size, chemical composition, and other characteristics. Only through the change of several generations of objects this class of objects acquires some features that, nevertheless, are considered to be typical for the whole class of objects.

Individuality as a way to increase evolutionary diversity

 Individual fates within evolution. It appears possible to maintain that with the formation of stars one observes the emergence of individual objects in nature, 'individuals' that, on the one hand, are rather similar, but have rather different individual fates much depending on circumstances of their birth and various contingencies. For example, stars with small masses (in which nuclear fusion occurs at a slow rate) can use all of their fuel (i.e., remain in the main sequence) for many billions of years. On the other hand, blue giants (in which the rate of fuel consumption is rapid and which lose most part of their mass due to their instability) burn out hundreds of times faster.

The stars can end their lives in a rather different way. Some of them, having lost one or a few outer layers, would cool, slowly transforming into cold bodies; some others may contract a few dozen times, or may end their lives with huge explosions blowing their matter into open space. Finally, a star may become a black hole that does not allow any matter to come out of its immensely compressed depths.

 Ontogenesis and phylogenesis. The evolution proceeds at various levels: through the development of its certain branch, a certain class, species and so on (and sometimes even at the level of an individual organism). In addition, applying biological terminology, at every level of evolution we find a combination of processes of ontogenesis and phylogenesis. Of course, within star-galaxy evolution the phylogenesis is represented much weaker than in the evolution of life. Nevertheless, it still appears possible to speak about the history of transformation of certain types of galaxies and stars, and, hence, up to a certain extent the cosmic phylogenesis does occur (see as above with respect to change of a few generations of stars and galaxies that differ from each other as regards their size, structure, and composition).

 Required and excessive variation as conditions of a search for new evolutionary trajectories. Within the processes described above one can observe the formation of the taxonomic diversity of space objects; we may even speak about occupying the evolutionary 'niches'. There emerge different types of stars and galaxies (see above). Such diversity is extremely important. Only the achievement of a necessary level of taxonomic and other diversity allows a search for ways to new evolutionary levels. This is sometimes denoted as the rule of necessary and excessive diversity (see Grinin, Markov, and Korotayev 2008: 68-72; for more details see also [START_REF] Panov | Cohesion of Social and Biological Evolution and the Limit of Its Acceleration[END_REF].

 Norm, averages, and deviation from a norm. Only when we find a sufficient diversity, it appears possible to speak about norm, average level, exceptions, and outliers. Scientists have long known that the breakthroughs to new forms usually happen at the periphery, and in those systems that diverge from the previous mainstream.

 Continuity, which actually means the emergence of a continuum of forms, sizes, life spans, and lifecycles, is rather characteristic for space objects. Thus, the stars can be presented as a continuum from heavier to lighter ones (whereas the latter become hardly distinguishable from planets). The types of planetary systems uniformly cover a wide range of parameters. There is also a sequence of phases in the transformation of cosmic clouds into stars: condensation of clouds -formation of protostars -formation of young stars, and up to the death of stars. The continuum of forms and sizes of objects may be observed at geological, biological, and social phases of the evolution.

Object, environment, competition, development systems, and

self-preservation  The relations between structure and environment. Multilevel systems (galaxygalaxy cluster -galaxy supercluster) act as systems of a higher order for stars, and, simultaneously, they create an environment that produces an enormous influence on those stars. A star directly interacts with its immediate environment (e.g., with neighboring stars because of the strong gravity which affects the movement of both stars), whereas with the distant environment the interaction proceeds at higher levels. Within star-galaxy evolution the role of environment is generally less important than at other evolutionary levels, because single stars are separated by great distances and that is why collide rather infrequently. On the other hand, one should not underestimate the role of the environment. For example, the role of the immediate environment is very important in systems of double, triple, or multiple stars. For a small galaxy the influence of neighboring larger galaxy may turn out to be fatal, if it leads to its absorption. External factors play the major role in changes (e.g., a large cosmic body can pass by a giant molecular clouds, there can occur a star explosion, and so on) and may trigger the process of formation of stars and galaxies (by launching the gas contraction process). Collisions of cosmic bodies may create new cosmic bodies -for example, there is a hypothesis that the Moon emerged as a result of the collision of some large objects with the Earth.

With the development of a certain form of evolution, its own laws and environment gain a growing influence on the development of its objects and subjects. For example, both abiotic nature and the biotic environment influence biological organisms. However, within a complex ecological environment, it is the intraspecies and interspecies competition that may have larger influence than any other natural factors, whereas within a complex social environment it is just the social surrounding that affects individuals and social systems more than the natural forces do. Thus, with the formation of star-galaxy structure of the Universe there emerged macro-objects which start to interact with environments which are larger by many orders of magnitude.

 The urge toward self-preservation and origins of the struggle for resources. Stars, galaxies, and planets (as well as other cosmic bodies) have their definite, quite structured, and preserved form. The 'struggle' for the preservation of those forms, the capacity to live and shine, the use of different layers to minimize energy losses lead to a slow but evident evolutionary development. This way the atomic composition of the Universe changes, whereas the diversity of variations of the existence of matter increases. On the one hand, the emergence of structures that strive for their preservation creates a wide range of interaction between the system and its environment; on the other hand, this creates a basis for the 'evolutionary search' and evolutionary advancement. This evolutionary paradox -the struggle for the self-preservation is the most important source for development -can be observed here in its full-fledged form. However, star-galaxy evolution demonstrates the emergence of this driving force which will become very important in biological evolution; and it appears to be the most important driving force in social evolution. This is the struggle for resources that among stars and galaxies may proceed in the form of weakening of another object or its destruction (e.g., through a direct transfer of energy and matter from one body to another), in the form of 'incorporation', 'capturing', that is 'annexation' of stars and star clusters by larger groups. We have already mentioned above galactic coalescences. Thus, some astronomers maintain that throughout a few billions of years our galaxy has 'conquered, robbed, and submitted' hundreds of small galaxies, as there are some evident 'immigrants' within our galaxy, including the second brightest star in the northern sky, Arcturus (Gibson and Ibata 2007: 30). It is widely accepted that emergence and expansion of a black hole may lead to the 'eating' of the matter of the nearby stars and galaxies. However, the 'eating capacity' of the black holes is greatly exaggerated in popular literature. In systems of double stars or in star-planet systems one may also observe such a form of interaction as the exchange of energy and resources.

Multilinearity

Multilinearity is one of the most important characteristics of evolution. Unfortunately, it does not get sufficient attention, and there is a tendency to reduce evolution to a single line -the one that has produced the highest complexity level, which is often interpreted as the main line of evolution. However, at every stage of evolutionary development one can find an interaction of a few lines that can have rather different futures. In other words, in addition to the main evolutionary line one can always identify a number of lateral ones. Firstly, they contribute to the increasing diversity; secondly, they allow expanding the range of search opportunities to move to new levels of development; thirdly, the lateral lines may partly enter the main evolutionary stream, enriching it. We quite often deal with two or more coexisting and comparable lines of development whose convergence may lead to a quantitative breakthrough and synergetic effect. Various lines of development may transform into each other. Elsewhere we have written a lot on the issue of social evolution in this context (see, e.g., [START_REF] Grinin | The Epoch of the Initial Politogenesis[END_REF]Grinin and Korotayev 2011;[START_REF] Bondarenko | Social Evolution: Alternatives and Variations (Introduction)[END_REF][START_REF] Grinin | From Early State to Global Society[END_REF].

 Classical forms and their analogues. The main and lateral lines of evolution may be considered in two dimensions: 1) horizontal (as regards complexity and functions), 2) vertical (concerning the version that would be realized later at higher evolutionary phases). It appears also possible to speak about classical versions and their analogues. Thus, various forms of aggregation and specialization of unicellulars can be regarded as analogues of multicellulars (see [START_REF] Eskov | Amazing Paleontology. History of the Earth and Life on It[END_REF], whereas various complex stateless polities can be regarded as state analogues (see [START_REF] Grinin | Political Development of the World System: A Formal Quantitative Analysis[END_REF][START_REF] Grinin | The Epoch of the Initial Politogenesis[END_REF][START_REF] Grinin | From Early State to Global Society[END_REF] for more detail). Classical forms and their analogues can transform into each other; however, these are just the analogues that tend to transform into classical forms, rather than the other way round (the latter may be regarded as a forced adaptation to sharply changing conditions, and sometimes even as a direct degeneration).

 Stars and molecular clouds: two parallel forms of existence of cosmic matter. In this respect we may consider stars and galaxies as the main line of evolution and the giant clouds as its lateral lines; the former may be denoted as 'classical forms', and the latter may be designated as 'analogues'. On the one hand, those forms actually transform into each other. Galaxies and stars emerge from giant molecular clouds, whereas stars through explosions and shedding their envelopes may transform into gas-dust cloud. On the other hand, giant molecular clouds are able to concentrate; the energy exchange occurs within them, and thus, in terms of gravity and structural complexity they are quite comparable to stars and galaxies. They generally have a rather complex 'Russian nesting doll' structure, whereby smaller and denser condensations are placed within larger and sparser ones (see Surkova 2005: 48). The Russian-doll structure is also typical for higher levels of evolution. Thus, smaller groups of social and gregarious animals constitute larger groups and tend to reproduce their structure. The same refers to social evolution, in particular to the non-centralized entities: for example, the tribal formations, whose constituent parts (lineages, clans, and sub-tribes) often reproduce the structure (and structural principles) of the tribe. That is why tribes can easily split and merge when necessary. The same is true of herds of gregarious animals.

Conclusion: The Formation of Various Evolutionary Lines at the Microworld Level

Astrophysical and astrochemical evolution. Almost from the very beginning of the development of the Universe (when the temperature reached thousands of Kelvin) chemical evolution emerges as accompanying physical and astrophysical evolution. Of course, chemical evolution also occurs within stars with the emergence of heavier elements. However, that was rather the formation of the basis for chemical evolution, because chemical processes involve the reactions which lead to the emergence of new substances. Such processes proceed, first of all, within gas-dust clouds where molecules emerge. Hydrogen molecules are absolutely prevalent quantitatively; however, molecules of water and some other substances also emerged. Chemical evolution goes on also on planets (where it combines with geological, or rather planetary evolution) as well as on small celestial bodies (asteroids and meteorites).

In contrast with biological and social forms which from their very start displayed substantially higher levels of organization of the matter, the chemical form (that emerged a rather short time after the physical form) did not represent a higher form of evolution for a rather long period of time. That is not to say that chemical evolution is not important in the framework of general stellar and galactic evolution; however, before the emergence of the Earth-like planet, the physical and chemical forms of organization of matter should be regarded as equally important; note also that they constantly transform into each other. The development of astrochemical evolution is not limited by the formation of simple nonorganic molecules. The processes of formation of molecules proceed further towards the formation of organic substances. More than hundred types of organic molecules have been detected in space (see [START_REF] Surdin | Stars Production[END_REF][START_REF] Surdin | Protostars. Where, How and Out of What Stars Form[END_REF][START_REF] Shklovsky | Stars: Their Birth, Life and Death[END_REF]. Naturally, this facilitated the emergence of life in a rather significant way.

The Formation of 'Preadaptations' as Points of Future Evolutionary Growth. Within the star-galaxy era the chemical form of development may be regarded as a 'preadaptation' for new levels of evolution. Let us note that in biology the term 'preadaptation' denotes those adaptations that may turn out to be useful in a different environment and to give significant advantages to those species that have them 9 -and generally -to give an impulse to the formation of new taxa. Within the Big History framework, the principle of 'preadaptation' means that at the level where a preadaptation emerges, it generally plays insignificant role; however, at a new evolutionary level such 'innovations' generally give evolutionary impulses. 10 Respectively, chemical compounds (as is common for preadaptations) do not mean much for cosmic evolution, they were rather 'in reserve' to reveal all their significance at the level of planetary evolution.

I would like to finish this article with a note on one more peculiarity of preadaptations. Appropriate conditions are necessary for their formation. Within biological evolution, the preadaptations often emerge in peculiar environments. Thus, it is supposed that the transformation of fins of the fleshy-finned fish (from which Amphibia descended) into primitive legs occurred within the environment of shallow waters that often dried out. In a similar way, within star-galaxy evolution the emergence of complex chemical compounds can take place only within certain structures of cosmic clouds that made their existence possible as they protected the molecules from cosmic radiation.

However, as with any evolutionary dead end, this does not mean an absolute stagnation. At present, in galaxy halos the dark matter is structured in certain smaller structures (see, e.g.,[START_REF] Diemand | Clumps and Streams in the Local Dark Matter Distribution[END_REF].

There might be an invisible halo consisting of dark matter behind the visible halo. It may be found in many (if not all) galaxies, whereby the diameter of the dark halo might exceed the diameter of the visible halo by an order of magnitude (see[START_REF] Ryabov | Поиски частиц темной материи[END_REF]Ryabov et al. : 1131)).

Thus, for every ten million red dwarfs we find only 1,000 giants and one supergiant(Surkova 2005: 26).

According to one of classifications (that might be more correct than the one reproduced below), it appears possible to subdivide all the stars just in two classes: a) massive stars (with a mass exceeding c. 10 solar masses), producing neutron stars and black holes, and b) non-massive ones producing white dwarfs(Lipunov 2008: 99).

For more details on the 'rule of evolutionary relay race' see[START_REF] Grinin | Macroevolution in Wild-life and Society. Moscow: LKI[END_REF]

For example, the Solar System emerged from the remnants of a supernova explosion. It is believed that due to this fact there are so many heavy and super-heavy elements on the Earth and other planets.

This omnivorous ability of hominids allowed their transition to hunting at a very early phase of the anthropogenesis.

On preadaptations in megaevolution see alsoGrinin, Korotayev, and Markov 2011: 159-160.


Alberto Apostolico

Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Martin Farach-Colton

Zvi Galil
email: galil@cc.gatech.edu

S Muthukrishnan

Forty Years of Suffix Trees

Keywords: pattern matching, string searching, bi-tree, suffix tree, dawg, suffix automaton, factor automaton, suffix array, FM-index, wavelet tree. 1. PROLOG

This paper reviews the first 40 years in the life of suffix trees, their many incarnations, and their applications. The paper is non-technical but assumes some familiarity with the structures and constructions discussed. It is not meant to be exhaustive. It is meant to be a tribute to a ubiquitous tool of string matching -the suffix tree and its variants -and one of the most persistent subjects of study in the theory of algorithms.

Both before and after 1843, the natural impulse when faced with some mysterious message has been to count frequencies of individual tokens or subassemblies in search of a clue. Perhaps one of the most intense and fascinating subjects for this kind of scrutiny have been bio-sequences. As soon as some such sequences became available, statistical analysts tried to link characters or blocks of characters to relevant biological functions. With the early examples of whole genomes emerging in the mid 1990's, it seemed natural to count the occurrences of all blocks of size 1, 2, etc., up to any desired length, looking for statistical characterizations of coding regions, promoter regions, etc. This review is not about cryptography. It is about a data structure and its variants, and the many surprising and useful features it carries. Among these is the fact that, to set up a statistical table of occurrences for all substrings (also called factors), of any length, of a text string of n characters, it only takes time and space linear in the length of the text string. While nobody would be so foolish as to solve the problem by first generating all exponentially many possible strings and then counting their occurrences one by one, a text string may still contain Θ(n 2 ) distinct substrings, so that tabulating all of them in linear space, never mind linear time, already seems puzzling.

Over the years, such structures have held center stage in text searching, indexing, statistics, and compression as well as in the assembly, alignment and comparison of biosequences. Their range of scope extends to areas as diverse as detecting plagiarism, finding surprising substrings in a text, testing the unique decipherability of a code, and more. Their impact on Computer Science and IT at large cannot be overstated. Text searching and Bioinformatics would not be the same without them. In 2013, the Combinatorial Pattern Matching symposium celebrated the 40th anniversary of the appearance of Weiner's paper [START_REF] Weiner | Linear pattern matching algorithms[END_REF] with a special session entirely dedicated to that event.

HISTORY BITS AND PIECES

At the dawn of "stringology," Don Knuth conjectured that the problem of finding the longest substring common to two long text sequences of total length n required Ω(n log n) time. An O(n log n)-time had been provided by Karp, Miller and Rosenberg [START_REF] Karp | Rapid identification of repeated patterns in strings, trees and arrays[END_REF]. That construction was destined to play a role in parallel pattern matching, but Knuth's conjecture was short lived: in 1973, Peter Weiner showed that the problem admitted an elegant linear-time solution [START_REF] Weiner | Linear pattern matching algorithms[END_REF], as long as the alphabet of the string was fixed. Such a solution was actually a byproduct of a construction he had originally set up for a different purpose, i.e., identifying any substring of a text file without specifying all of them. In doing so, Weiner introduced the notion of a textual inverted index that would elicit refinements, analyses and applications for forty years and counting, a feature hardly shared by any other data structure.

Weiner's original construction processed the text file from right to left. As each new character was read in, the structure, which he called a "bi-tree", would be updated to accommodate longer and longer suffixes of the text file. Thus this was an inherently off-line construction, since the text had to be known in its entirety before the construction could begin. Alternatively, one could say that the algorithm would build the structure for the reverse of the text on-line. About three years later, Ed McCreight provided a left-to-right algorithm and changed the name of the structure to "suffix tree," a name that would stick [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF].

Let x be a string of n -1 symbols over some alphabet Σ and $ an extra character not in Σ. The expanded suffix tree Tx associated with x is a digital search tree collecting all suffixes of x$. Specifically, Tx is defined as follows.

1. Tx has n leaves, labeled from 1 to n.

2. Each arc is labeled with a symbol of Σ ∪ {$}. For any i, 1 ≤ i ≤ n, the concatenation of the labels on the path from the root of Tx to leaf i is precisely the suffix sufi = xixi+1...xn-1$.

3. For any two suffixes sufi and sufj of x$, if wij is the longest common prefix that sufi and sufj have in common, then the path in Tx relative to wij is the same for sufi and sufj.

An example of expanded suffix tree is given in Figure 1.

The tree can be interpreted as the state transition diagram of a deterministic finite automaton where all nodes and leaves are final states, the root is the initial state, and the labeled arcs, which are assumed to point downwards, represent part of the state-transition function. The state transitions not specified in the diagram lead to a unique non-final sink state. Our automaton recognizes the (finite) language consisting of all substrings of string x. This observation also clarifies how the tree can be used in an on-line search: letting y be the pattern, we follow the downward path in the tree in response to consecutive symbols of y, one symbol at a time. Clearly, y occurs in x if and only if this process leads to a final state. In terms of Tx, we say that the locus of a string y is the node α, if it exists, such that the path from the root of Tx to α is labeled y.

An algorithm for the direct construction of the expanded Tx (often called suffix trie) is readily derived (see Figure 2). We start with an empty tree and add to it the suffixes of x$ one at a time. This procedure takes time Θ(n 2 ) and O(n 2 ) space, however, it is easy to reduce space to O(n) thereby producing a suffix tree in compact form (Figure 3). Once this is done, it becomes possible to aim for an expectedly non-trivial O(n) time construction. At the CPM Conference of 2013, McCreight revealed that his O(n) time construction was not born as an alternative to Weiner's: he had developed it in an effort to understand Weiner's paper, but when he showed it to Weiner asking him to confirm that he had understood that paper the answer was "No, but you have come up with an entirely different and elegant construction!" In unpublished lecture notes of 1975, Vaughan Pratt displayed the duality of this structure and Weiner's "repetition finder" [START_REF] Pratt | Improvements and applications for the Weiner repetition finder[END_REF]. McCreight's algorithm was still inherently off-line, and it immediately triggered a search for an on-line version. Some partial attempts at an on-line algorithm were made, but such a variant had to wait almost two decades for Esko Ukkonen's paper in 1995 [START_REF] Ukkonen | On-line construction of suffix trees[END_REF]. In all these linear-time constructions, linearity was based on the assumption of a finite alphabet and took Θ(n log n) time without that assumption. In 1997, Martin Farach introduced an algorithm that abandoned the onesuffix-at-time approach prevalent until then; this algorithm gives a linear-time reduction from suffix-tree construction to character sorting, and thus is optimal for all alphabets [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF]. In particular, it runs in linear time for a larger class of alphabets, for example, when the alphabet size is polynomial in input length.

Around 1984, Anselm Blumer et al. [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF] and Maxime Crochemore [START_REF] Crochemore | Transducers and repetitions[END_REF] exposed the surprising result that the smallest finite automaton recognizing all and only the suffixes of a string of n characters has only O(n) states and edges. Initially coined a directed acyclic word graph (DAWG), it can even be further reduced if all states are terminal states [START_REF] Crochemore | Transducers and repetitions[END_REF]. It then accepts all substrings of the string and is called the factor/substring automaton. There is a nice relation between the index data structures when the string has no end-marker and its suffixes are marked with terminal states in the trie. The insertion of suffix sufi (i = 1, 2, ..., n) consists of two phases. In the first phase, we search for sufi in Ti-1. Note that the presence of $ guarantees that every suffix will end in a distinct leaf. Therefore, this search will end with failure sooner or later. At that point, we will have identified the longest prefix of sufi that has a locus (i.e., a terminal node) in Ti-1. Let headi (abcab in the example) be this prefix and α the locus of headi. We can write sufi = headi • taili with taili (a$ in the example) nonempty. In the second phase, we need to add to Ti-1 a path leaving node α and labeled taili. This achieves the transformation of Ti-1 into Ti.

Then, the suffix tree is the edge-compacted version of the trie and its number of nodes can be minimized like with any automaton thereby providing the compact DAWG of the string. Permuting the two operations, compaction and minimization, leads to the same structure. Apparently Anatoli Slissenko (see Appendix) ended up with a similar structure for his work on the detection of repetitions in strings. These automata provide another more efficient counterexample to Knuth's conjecture when they are used, against the grain, as pattern matching machines (see Figure 4).

The appearance of suffix trees dovetailed with some interesting and independent developments in information theory. In his famous approach to the notion of information, Kolmogorov equated the information or structure in a string to the length of the shortest program that would be needed to produce that string by a Universal Turing Machine. The unfortunate thing is that this measure is not computable and even if it were, most long strings are incompressible (i.e., lack a short program producing them), since there are increasingly many long strings and comparatively much fewer short programs (themselves strings).

The regularities exploited by Kolmogorov's universal and omniscient machine could be of any conceivable kind, but what if one limited them to the syntactic redundancies affecting a text in the form of repeated substrings? If a string is repeated many times one could profitably encode all occurrences by a pointer to a common copy. This copy could be internal or external to the text. In the former case one could have pointers going in both directions or only in one direction, allow or forbid nesting of pointers, etc. In his doctoral thesis, Jim Storer showed that virtually all such "macro schemes" are intractable, except one. Not long before that, in a landmark paper entitled "On the Complexity of Finite Sequences" [START_REF] Lempel | On the complexity of finite sequences[END_REF], Abraham Lempel and Jacob Ziv had proposed a variable-to-block encoding, based on a simple parsing of the text with the feature that the compression achieved would match, in the limit, that produced by a compressor tailored to the source probabilities. Thus, by a remarkable alignment of stars, the compression method brought about by Lempel and Ziv was not only optimal in the information theoretic sense, but it found an optimal, linear-time implementation by the suffix tree, as was detailed immediately by Michael Rodeh, Vaugham Pratt and Shimon Even [START_REF] Rodeh | Linear algorithm for data compression via string matching[END_REF].

In his original paper, Weiner listed a few applications of his "bi-tree" including most notably off-line string searching: preprocessing a text file to support queries that return the occurrences of a given pattern in time linear in the length of the pattern. And of course, the "bi-tree" addressed Despite the fact that it is an index on the string, the same automaton can be used as a pattern-matching machine to locate substrings of "bananas" in another text or to compute their longest common substring. The process runs on-line on the second string. Assume for example "bana" has just been scanned from the second string and the current state of the automaton is state 4. If the next letter is "n", the common substring is "banan" of length 5 and the new state is 5. If the next letter is "s", the failure link is used and from state 3' corresponding to a common substring "ana" of length 3 we get the common substring "anas" with the new state 7. If the next letter is "b", iterating the failure link leads to state 0 and we get the common substring "b" with the new state 1. Finally, any other next letter will produce the empty common substring and state 0.

Knuth's conjecture, by showing how to find the longest substring common to two files in linear time for a finite alphabet. There followed unpublished notes by Pratt entitled "Improvements and Applications for the Weiner Repetition Finder" [START_REF] Pratt | Improvements and applications for the Weiner repetition finder[END_REF]. A decade later, Alberto Apostolico would list more applications in a paper entitled "The Myriad Virtues of Suffix Trees" [START_REF] Apostolico | The myriad virtues of suffix trees[END_REF], and two decades later suffix trees and companion structures with their applications gave rise to several chapters in reference books by Crochemore and Rytter, Dan Gusfield, and Crochemore, Hancart and Lecroq (see Appendix).

The space required by suffix trees has been a nuisance in applications where they were needed the most. With genomes on the order of gigabytes, for instance, the space difference between 20 times larger than the source versus, say, only 11 times larger, can be substantial. For a few lustra, Stefan Kurtz and his co-workers devoted their effort to cleverly allocating the tree and some of its companion structures [START_REF] Kurtz | Reducing the space requirements of suffix trees[END_REF]. In 2001 David R. Clark and J. Ian Munro proposed one of the best space-saving methods on secondary storage [START_REF] Clark | Efficient suffix trees on secondary storage[END_REF]. Clark and Munro's "succinct suffix tree" sought to preserve as much of the structure of the suffix tree as possible. Udi Manber and Eugene W. Myers took a different approach, however. In 1990, they introduced the "suffix array" [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF], which eliminated most of the structure of the suffix tree, but was still able to implement many of the same operations, requiring space equal to 2 integers per text character and searching in time O(|P | + log n) (reducible to 1 by accepting search time O(|P | log n)). The suffix array stores the suffixes of the input in lexicographic order and can be seen as the sequence of leaves' labels as found in the suffix tree by a preorder traversal that would expand each node according to the lexicographic order. Although the suffix array seemed at first to be a different data structure than the suffix tree, the distinction has receded. For example, Manber and Myers's original construction of the suffix array took O(n log n) time for any alphabet, but the suffix array could be constructed in linear time from the suffix tree for any alphabet. In 2001, Toru Kasai et al. [START_REF] Kasai | Linear-time longest-common-prefix computation in suffix arrays and its applications[END_REF] showed that the suffix tree could be constructed in linear time from the suffix array. Therefore the suffix array was shown to be a succinct representation of the suffix tree. In 2003, three groups (see Appendix) presented three different modifications of Farach's algorithm for suffix tree construction to give the first linear-time algorithms for directly constructing the suffix array; that is, the first linear-time algorithms for computing suffix arrays that did not first compute the full suffix tree. Since then, there have been many algorithms for fast construction of suffix arrays, notably by Nong, Zhang and Chan [START_REF] Nong | Two efficient algorithms for linear time suffix array construction[END_REF], which is linear time and fast in practice. With fast construction algorithms and small space required, the suffix array is the suffix-tree variant that has gained the most widespread adoption in software systems. A more recent succinct suffix tree and array, which take O(n) bits to represent for a binary alphabet (O(n log σ) bits otherwise), was presented by Grossi and Vitter [START_REF] Grossi | Compressed suffix arrays and suffix trees with applications to text indexing and string matching[END_REF].

Actually, the histories of suffix trees and compression are tightly intertwined. This should not come as a surprise, since the redundancies that pattern discovery tries to unearth are ideal candidates to be removed for purposes of compression. In 1994, M. Burrows and D. J. Wheeler proposed a breakthrough compression method based on suffix sorting [START_REF] Burrows | A block-sorting lossless data compression algorithm[END_REF]. Circa 1995, Amihood Amir, Gary Benson and Martin Farach posed the problem of searching in compressed texts [START_REF] Amir | Let sleeping files lie: Pattern matching in Z-compressed files[END_REF]. In 2000, Paolo Ferragina and Giovanni Manzini introduced the FM-index, a compressed suffix array based on the Burrows-Wheeler transform [START_REF] Ferragina | Opportunistic data structures with applications[END_REF]. This structure, which may be smaller than the source file, supports searching without decompression. This was extended to compressed tree indexing problems in [START_REF] Ferragina | Compressing and indexing labeled trees, with applications[END_REF] using a modification of the Burrows-Wheeler transform.

FALLOUT, EXTENSIONS AND CHALLENGES

As highlighted in our prolog, there has been hardly any application of text processing that did not need these indexes at one point or another. A prominent case has been searching with errors, a problem first efficiently tackled in 1985 by Gad Landau in his PhD thesis [START_REF] Landau | String matching in erroneus input[END_REF]. In this kind of search, one looks for substrings of the text that differ from the pattern in a limited number of errors such as a single character deletion, insertion or substitution. To efficiently solve this problem, Landau combined Suffix Trees with a clever solution to the so-called lowest common ancestor (LCA) problem. The LCA problem assumes that a rooted tree is given and then it seeks, for any pair of nodes, the lowest node in the tree that is an ancestor of both [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF]. It is seen that following a linear-time preprocessing of the tree any LCA query can be answered in constant time. Landau used LCA queries on Suffix Trees to perform constant-time jumps over segments of the text that would be guaranteed to match the pattern. When k errors are allowed, the search for an occurrence at any given position can be abandoned after k such jumps. This leads to an algorithm that searches for a pattern with k errors in a text of n characters in O(nk) steps.

Among the basic primitives supported by suffix trees and arrays, one finds of course the already mentioned search for a pattern in a text in time proportional to the length of the pattern rather than the text. In fact, it is even possible to enumerate occurrences in time proportional to their number and, with trivial preprocessing of the tree, tell the total number of occurrences for any query pattern in time proportional to the pattern size. The problem of finding the longest substring appearing twice in a text or shared between two files has been already mentioned: this is probably where it all started. A germane problem is that of detecting squares, repetitions and maximal periodicities in a text, a problem rooted in work by Axel Thue dated more than a century ago with multiple contemporary applications in compression and DNA analysis. A square is a pattern consisting of two consecutive occurrences of the same string. Suffix trees have been used to detect in optimal O(n log n) time all squares (or repetitions) in a text, each with its set of starting positions [5], and later to find and store all distinct square substrings in a text in linear time. Squares play a role in an augmentation of the suffix tree suitable to report, for any query pattern, the number of its non-overlapping occurrences [START_REF] Apostolico | Data structures and algorithms for the strings statistics problem[END_REF][START_REF] Brodal | Solving the string statistics problem in time O(n log n)[END_REF].

There are multiple uses of suffix trees in setting up some kind of signature for text strings, as well as measures of similarity or difference. Among the latter, there is the problem of computing the forbidden or absent words of a text, which are minimal strings that do not appear in the text (while all their proper substrings do) [START_REF] Béal | Minimal forbidden words and symbolic dynamics[END_REF][START_REF] Crochemore | Automata and forbidden words[END_REF]. Such words lead to, among other things, an original approach to text compression [START_REF] Crochemore | Data compression using antidictonaries[END_REF]. Once regarded as the succinct representation of the "bag-of-words" of a text, suffix trees can be used to assess the similarity of two text files, thereby supporting clustering, document classification and even phylogeny [START_REF] Apostolico | Efficient tools for comparative substring analysis[END_REF][START_REF] Chairungsee | Using minimal absent words to build phylogeny[END_REF][START_REF] Ulitsky | The average common substring approach to phylogenomic reconstruction[END_REF].

Intuitively, this is done by assessing how much the trees for the two input sequences have in common. Suitably enriched with the probability of the substring ending at each node, a tree can be used to detect surprisingly over-represented substrings of any length [START_REF] Apostolico | Monotony of surprise and large-scale quest for unusual words[END_REF], e.g., in the quest of promoter regions in biosequences.

The suffix tree of the concatenation of say, k ≥ 2 text files, supports efficient solutions to problems arising in domains ranging from plagiarism detection to motif discovery in biosequences. The need for k distinct end-markers poses some subtleties in maintaining linear time, for which the reader is referred to [START_REF] Gusfield | Algorithms on strings, trees and sequences: computer science and computational biology[END_REF]. In its original form, the problem of indexing multiple texts was called the "color problem" and seeks to report, for any given query string and in time linear in the query, how many documents out of the total of k contain at least one occurrence of the query. A simple and elegant solution was given in 1992 by Lucas C. K. Hui [START_REF] Hui | Color set size problem with applications to string matching[END_REF]. Recently, the combined suffix trees of many strings (also known as the generalized suffix tree) was used to solve a variety of document listing problems. Here, a set of text documents are preprocessed as a combined suffix tree. The problem is to return the list of all documents that contain a query pattern in time proportional to the number of such documents, not to the total number of occurrences (occ) which can be significantly larger. This problem was solved in [START_REF] Muthukrishnan | Efficient algorithms for document listing problems[END_REF] by reducing it to Range Minimum Queries. This basic document listing problem has since been extended to many other problems including listing the top-k in various string and information distances. For example, in [START_REF] Hon | Space-efficient framework for top-k string retrieval problems[END_REF], the structure of generalized suffix tree is crucially used to design a linear machine-word data structure to return the top-k most frequent documents containing a pattern p in time nearly linear in pattern size.

One surprising variant of the suffix tree was introduced by Brenda Baker for purposes of detection of plagiarism in student reports as well as optimization in software development [START_REF] Baker | Parameterized duplication in strings: Algorithms and an application to software maintenance[END_REF]. This variant of pattern matching, called "parameterized matching", enables one to find program segments that are identical up to a systematic change of parameters, or substrings that are identical up to a systematic relabeling or permutation of the characters in the alphabet.

One obvious extension of the notion of a suffix tree is to more than one dimension, albeit the mechanics of the extension itself are far from obvious [START_REF] Na | Two-dimensional pattern indexing[END_REF]. Among more distant relatives, one finds "wavelet trees". Originally proposed as a representation of compressed suffix arrays [START_REF] Grossi | High-order entropy-compressed text indexes[END_REF], wavelet trees enable one to perform on general alphabets the ranking and selection primitives previously limited to bit vectors, and more.

The list could go on and on, but the scope of this paper was not meant to be exhaustive. Actually, after forty years of unrelenting developments, it is fair to assume that the list will continue to grow. Open problems also abound. For instance, many of the observed sequences are expressed in numbers rather than characters, and in both cases are affected by various types of errors. While the outcome of a two character comparison is just one bit, two numbers can be more or less close, depending on their difference or some other metric. Likewise, two text strings can be more or less similar, depending on the number of elementary steps necessary to change one in the other. The most disruptive aspect of this framework is the loss of the transitivity property that leads to the most efficient exact string matching solutions.

And yet indexes capable of supporting fast and elegant approximate pattern queries of the kind just highlighted would be immensely useful. Hopefully, they will come up soon and, in time, have their own 40th anniversary celebration.

Figure 1 :

 1 Figure 1: The expanded suffix tree of the string x = abcabcaba

Figure 2 :

 2 Figure2: Building an expanded suffix tree by insertion of consecutive suffixes (showing here the insertion of abcaba$). The insertion of suffix sufi (i = 1, 2, ..., n) consists of two phases. In the first phase, we search for sufi in Ti-1. Note that the presence of $ guarantees that every suffix will end in a distinct leaf. Therefore, this search will end with failure sooner or later. At that point, we will have identified the longest prefix of sufi that has a locus (i.e., a terminal node) in Ti-1. Let headi (abcab in the example) be this prefix and α the locus of headi. We can write sufi = headi • taili with taili (a$ in the example) nonempty. In the second phase, we need to add to Ti-1 a path leaving node α and labeled taili. This achieves the transformation of Ti-1 into Ti.

Figure 3 :

 3 Figure3: A suffix tree in compact form. This is obtained by first collapsing every chain formed by nodes with only one child into a single arc. The resulting compact version of Tx has at most n internal nodes, since there are n + 1 leaves in total and every internal node is branching. The labels of the generic arc are now a substring, rather than a symbol of x$. However, arc labels can be expressed by suitable pairs of pointers to a common copy of x$ thus achieving O(n) space bound overall.

Figure 4 :

 4 Figure 4: The compact suffix tree (top) and the suffix automaton (bottom) of the string "bananas". Failure links are represented by the dashed arrows.Despite the fact that it is an index on the string, the same automaton can be used as a pattern-matching machine to locate substrings of "bananas" in another text or to compute their longest common substring. The process runs on-line on the second string. Assume for example "bana" has just been scanned from the second string and the current state of the automaton is state 4. If the next letter is "n", the common substring is "banan" of length 5 and the new state is 5. If the next letter is "s", the failure link is used and from state 3' corresponding to a common substring "ana" of length 3 we get the common substring "anas" with the new state 7. If the next letter is "b", iterating the failure link leads to state 0 and we get the common substring "b" with the new state 1. Finally, any other next letter will produce the empty common substring and state 0.

Acknowledgements: We are grateful to Ed McCreight, Ronnie Martin, Vaughan Pratt, Peter Weiner, and Jacob Ziv for discussions and help. We are indebted to the Referees for their careful scrutiny of an earlier version of the paper, which led to many improvements.