# Using Formal Grammars as Musical Genome
## 1 Introduction
### Automated Composition  
The digital era brought yet another step in the evolution of musical genres [3] and the development of algorithmic composition [4]. Some works at the early age were: an unpublished work by [PERSON] and [PERSON] in 1955 [5], with an implementation of [PERSON]'s dice game and a generator of melodic lines using stochastic transitional probabilities; the [PERSON] and [PERSON]'s Illica Suite [6], based on Markov chains and rule systems; and MUSI-COMP by [PERSON] [7], implementing some methods used by [PERSON]'s Xenakis's stochastic algorithms in the early 1960s, working as CAAC [7]. In 1961, a dedicated computer was able to compose new melodies related to previous ones by using Markov processes [8]and in 1963, [PERSON]'s algorithm applied classical AI techniques (hierarchical search with backtracking) [9]. Machines were becoming less expensive and more powerful and the field of algorithmic composition grew along, intersecting the field of Artificial Intelligence.  
Composing music imitating an existing corpus has been approached quite successfully. For example, [PERSON]'s EMI [10] was able to analyze a musical style, extract patterns of short musical sequences and determine how to use them when composing in that style. More recently, with the rise of neural networks, while not being as widespread as other forms of arts that use Generative Adversarial Networks [11] and other methods, we find many examples of systems following this imitating approach. For example, using long short-term memory (LSTM) recurrent network to learn complete musical structures and produce music in that style [12] or networks based on gate recurrent units (GRU) to produce monophonic melodies by learning from a corpus of different styles [13].  
On the other hand, composing with no creative input has been a harder problem for computational intelligence, partly because of the difficulty of assessing the results, although some frameworks have been proposed [2; 14; 15; 16]. Genetic algorithms have proven to be very suitable to produce novel musical content. In 1994, GenJam [17] was an interactive method to create jazz melodies. More examples of interactive genetic algorithms are Vox Populi [18], based on evolving chords, and Darwin Tunes [19] that studied the evolution of short audio loops. There has been a wide variety of automatic musical fitness assessments. [PERSON] and [PERSON] [19] recently proposed a method to create jazz melodies, encoding explicitly the musical variables in the chromosomes and using a fitness function based on the theory of harmony and note patterns. However, evolutionary and developmental (evolve) methods, using indirect encoding, although more complex to design, are meant to provide more unpredictable and diverse results. Musical Organisms [20] defined a gene regulatory network and focused on structural modularity, hierarchy and repetition as a common principle of living beings and music to produce musical scores. Formal grammars have been suitable to express this inner structured nature of music, for example to study melody [21], musical structure [22] or harmony in tonal music, even with a generative approach [23]. L-systems [24] in particular have been frequently used as representational models in evo-devo processes due to their simplicity, sometimes with an interactive fitness and studying ways of visualizing music [25; 26].  
In Section 2 we present an approach of encoding music by means of L-systems and context-free grammars and then compose music by evolution of these formal models. The two representational systems are actually part of different programs developed from the same principles, but adapted for the composition of both atonal and tonal music. These mathematical systems, which are able to represent self-similarity encoding compositional and performance properties, can evolve as to produce valid and esthetic music scores and then synthesize them in multiple audio formats.