Auditory agnosia

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Auditory_agnosia

Auditory agnosia is a form of agnosia that manifests itself primarily in the inability to recognize or differentiate between sounds. It is not a defect of the ear or "hearing", but rather a neurological inability of the brain to process sound meaning. While auditory agnosia impairs the understanding of sounds, other abilities such as reading, writing, and speaking are not hindered. It is caused by bilateral damage to the anterior superior temporal gyrus, which is part of the auditory pathway responsible for sound recognition, the auditory "what" pathway.

Persons with auditory agnosia can physically hear the sounds and describe them using unrelated terms, but are unable to recognize them. They might describe the sound of some environmental sounds, such as a motor starting, as resembling a lion roaring, but would not be able to associate the sound with "car" or "engine", nor would they say that it was a lion creating the noise. All auditory agnosia patients read lips in order to enhance the speech comprehension.

It is yet unclear whether auditory agnosia (also called general auditory agnosia) is a combination of milder disorders, such auditory verbal agnosia (pure word deafness), non-verbal auditory agnosia, amusia and word-meaning deafness, or a mild case of the more severe disorder, cerebral deafness. Typically, a person with auditory agnosia would be incapable of comprehending spoken language as well as environmental sounds. Some may say that the milder disorders are how auditory agnosia occurs. There are few cases where a person may not be able to understand spoken language. This is called verbal auditory agnosia or pure word deafness. Nonverbal auditory agnosia is diagnosed when a person’s understanding of environmental sounds is inhibited. Combined, these two disorders portray auditory agnosia. The blurriness between the combination of these disorders may lead to discrepancies in reporting. As of 2014, 203 patients with auditory perceptual deficits due to CNS damage were reported in the medical literature, of which 183 diagnosed with general auditory agnosia or word deafness, 34 with cerebral deafness, 51 with non-verbal auditory agnosia-amusia and 8 word meaning deafness (for a list of patients see).

History

A relationship between hearing and the brain was first documented by Ambroise Paré, a 16th century battlefield doctor, who associated parietal lobe damage with acquired deafness (reported in Henschen, 1918). Systematic research into the manner in which the brain processes sounds, however, only began toward the end of the 19th century. In 1874, Wernicke was the first to ascribe to a brain region a role in auditory perception. Wernicke proposed that the impaired perception of language in his patients was due to losing the ability to register sound frequencies that are specific to spoken words (he also suggested that other aphasic symptoms, such as speaking, reading and writing errors occur because these speech specific frequencies are required for feedback). Wernicke localized the perception of spoken words to the posterior half of the left STG (superior temporal gyrus). Wernicke also distinguished between patients with auditory agnosia (which he labels as receptive aphasia) with patients who cannot detect sound at any frequency (which he labels as cortical deafness).

In 1877, Kussmaul was the first to report auditory agnosia in a patient with intact hearing, speaking, and reading-writing abilities. This case-study led Kussmaul to propose of distinction between the word perception deficit and Wernicke's sensory aphasia. He coined the former disorder as "word deafness". Kussmaul also localized this disorder to the left STG. Wernicke interpreted Kussmaul's case as an incomplete variant of his sensory aphasia.

In 1885, Lichtheim also reported of an auditory agnosia patient. This patient, in addition to word deafness, was impaired at recognizing environmental sounds and melodies. Based on this case study, as well as other aphasic patients, Lichtheim proposed that the language reception center receives afferents from upstream auditory and visual word recognition centers, and that damage to these regions results in word deafness or word blindness (i.e., alexia), respectively. Because the lesion of Lichtheim's auditory agnosia patient was sub-cortical deep to the posterior STG (superior temporal gyrus), Lichtheim renamed auditory agnosia as "sub-cortical speech deafness".

The language model proposed by Wernicke and Lichtheim wasn't accepted at first. For example, in 1897 Bastian argued that, because aphasic patients can repeat single words, their deficit is in the extraction of meaning from words. He attributed both aphasia and auditory agnosia to damage in Lichtheim's auditory word center. He hypothesized that aphasia is the outcome of partial damage to the left auditory word center, whereas auditory agnosia is the result of complete damage to the same area. Bastian localized the auditory word center to the posterior MTG (middle temporal gyrus).

Other opponents to the Wernicke-Lichtheim model were Sigmund Freud and Carl Freund. Freud (1891) suspected that the auditory deficits in aphasic patients was due to a secondary lesion to cochlea. This assertion was confirmed by Freund (1895), who reported two auditory agnosia patients with cochlear damage (although in a later autopsy, Freund reported also the presence of a tumor in the left STG in one of these patients). This argument, however, was refuted by Bonvicini (1905), who measured the hearing of an auditory agnosia patient with tuning forks, and confirmed intact pure tone perception. Similarly, Barrett's aphasic patient, who was incapable of comprehending speech, had intact hearing thresholds when examined with tuning forks and with a Galton whistle. The most adverse opponent to the model of Wernicke and Lichtheim was Marie (1906), who argued that all aphasic symptoms manifest because of a single lesion to the language reception center, and that other symptoms such as auditory disturbances or paraphasia are expressed because the lesion encompasses also sub-cortical motor or sensory regions.

In the following years, increasing number of clinical reports validated the view that the right and left auditory cortices project to a language reception center located in the posterior half of the left STG, and thus established the Wernicke-Lichtheim model. This view was also consolidated by Geschwind (1965) who reported that, in humans, the left planum temporale is larger in the left hemisphere than on the right. Geschwind interpreted this asymmetry as anatomical verification for the role of left posterior STG in the perception of language.

The Wernicke-Lichtheim-Geschwind model persisted throughout the 20th century. However, with the advent of MRI and its usage for lesion mapping, it was shown that this model is based on incorrect correlation between symptoms and lesions. Although this model is considered outdated, it is still widely mentioned in Psychology and medical textbooks, and consequently in medical reports of auditory agnosia patients. As will be mentioned below, based on cumulative evidence the process of sound recognition was recently shifted to the left and right anterior auditory cortices, instead of the left posterior auditory cortex.

Related disorders

After auditory agnosia was first discovered, subsequent patients were diagnosed with different types of hearing impairments. In some reports, the deficit was restricted to spoken words, environmental sounds or music. In one case study, each of the three sound types (music, environmental sounds, speech) was also shown to recover independently (Mendez and Geehan, 1988-case 2). It is yet unclear whether general auditory agnosia is a combination of milder auditory disorders, or whether the source of this disorder is at an earlier auditory processing stage.

Cerebral deafness

Cerebral deafness (also known as cortical deafness or central deafness) is a disorder characterized by complete deafness that is the result of damage to the central nervous system. The primary distinction between auditory agnosia and cerebral deafness is the ability to detect pure tones, as measured with pure tone audiometry. Using this test, auditory agnosia patients were often reported capable of detecting pure tones almost as good as healthy individuals, whereas cerebral deafness patients found this task almost impossible or they required very loud presentations of sounds (above 100 dB). In all reported cases, cerebral deafness was associated with bilateral temporal lobe lesions. A study that compared the lesions of two cerebral deafness patients to an auditory agnosia patient concluded that cerebral deafness is the result of complete de-afferentation of the auditory cortices, whereas in auditory agnosia some thalamo-cortical fibers are spared. In most cases the disorder is transient and the symptoms mitigate into auditory agnosia (although chronic cases were reported). Similarly, a monkey study that ablated both auditory cortices of monkeys reported of deafness that lasted 1 week in all cases, and that was gradually mitigated into auditory agnosia in a period of 3–7 weeks.

Pure word deafness

Since the early days of aphasia research, the relationship between auditory agnosia and speech perception has been debated. Lichtheim (1885) proposed that auditory agnosia is the result of damage to a brain area dedicated to the perception of spoken words, and consequently renamed this disorder from 'word deafness' to 'pure word deafness'. The description of word deafness as being exclusively for words was adopted by the scientific community despite the patient reported by Lichtheim's who also had more general auditory deficits. Some researchers who surveyed the literature, however, argued against labeling this disorder as pure word deafness on the account that all patients reported impaired at perceiving spoken words were also noted with other auditory deficits or aphasic symptoms. In one review of the literature, Ulrich (1978) presented evidence for separation of word deafness from more general auditory agnosia, and suggested naming this disorder "linguistic auditory agnosia" (this name was later rephrased into "verbal auditory agnosia"). To contrast this disorder with auditory agnosia in which speech repetition is intact (word meaning deafness), the name "word sound deafness" and "phonemic deafness" (Kleist, 1962) were also proposed. Although some researchers argued against the purity of word deafness, some anecdotal cases with exclusive impaired perception of speech were documented. On several occasions, patients were reported to gradually transition from pure word deafness to general auditory agnosia/cerebral deafness or recovery from general auditory agnosia/cerebral deafness to pure word deafness.

In a review of the auditory agnosia literature, Phillips and Farmer showed that patients with word deafness are impaired in their ability to discriminate gaps between click sounds as long as 15-50 milliseconds, which is consistent with the duration of phonemes. They also showed that patients with general auditory agnosia are impaired in their ability to discriminate gaps between click sounds as long as 100–300 milliseconds. The authors further showed that word deafness patients liken their auditory experience to hearing foreign language, whereas general auditory agnosia described speech as incomprehensible noise. Based on these findings, and because both word deafness and general auditory agnosia patients were reported to have very similar neuroanatomical damage (bilateral damage to the auditory cortices), the authors concluded that word deafness and general auditory agnosia is the same disorder, but with a different degree of severity.

Pinard et al also suggested that pure word deafness and general auditory agnosia represent different degrees of the same disorder. They suggested that environmental sounds are spared in the mild cases because they are easier to perceive than speech parts. They argued that environmental sounds are more distinct than speech sounds because they are more varied in their duration and loudness. They also proposed that environmental sounds are easier to perceive because they are composed of a repetitive pattern (e.g., the bark of a dog or the siren of the ambulance).

Auerbach et al considered word deafness and general auditory agnosia as two separate disorders, and labelled general auditory agnosia as pre-phonemic auditory agnosia and word deafness as post-phonemic auditory agnosia. They suggested that pre-phonemic auditory agnosia manifests because of general damage to the auditory cortex of both hemispheres, and that post-phonemic auditory agnosia manifests because of damage to a spoken word recognition center in the left hemisphere. Recent evidence, possibly verified Auerbach hypothesis, since an epileptic patient who undergone electro-stimulation to the anterior superior temporal gyrus was demonstrated a transient loss of speech comprehension, but with intact perception of environmental sounds and music.

Non-verbal auditory agnosia

The term auditory agnosia was originally coined by Freud (1891) to describe patients with selective impairment of environmental sounds. In a review of the auditory agnosia literature, Ulrich re-named this disorder as non-verbal auditory agnosia (although sound auditory agnosia and environmental sound auditory agnosia are also commonly used). This disorder is very rare and only 18 cases have been documented. In contradiction to pure word deafness and general auditory agnosia, this disorder is likely under-diagnosed because patients are often not aware of their disorder, and thus don't seek medical intervention.

Throughout the 20th century, all reported non-verbal auditory agnosia patients had bilateral or right temporal lobe damage. For this reason, the right hemisphere was traditionally attributed with the perception of environmental sounds. However, Tanaka et al reported 8 patients with non-verbal auditory agnosia, 4 with right hemisphere lesions and 4 with left hemisphere lesions. Saygin et al also reported a patient with damage to the left auditory cortex.

The underlying deficit in non-verbal auditory agnosia appears to be varied. Several patients were characterized by impaired discrimination of pitch whereas others reported with impaired discrimination of timbre and rhythm (discrimination of pitch was relatively preserved in one of these cases). In contrast, to patients with pure word deafness and general auditory agnosia, patients with non-verbal auditory agnosia were reported impaired at discriminating long gaps between click sounds, but impaired at short gaps. A possible neuroanatomical structure that relays longer sound duration was suggested by Tanaka et al. By comparing the lesions of two cortically deaf patients with the lesion of a word deafness patient, they proposed the existence of two thalamocortical pathways that inter-connect the MGN with the auditory cortex. They suggested that spoken words are relayed via a direct thalamocortical pathway that passes underneath the putamen, and that environmental sounds are relayed via a separate thalamocortical pathway that passes above the putamen near the parietal white matter.

Amusia

Auditory agnosia patients are often impaired in the discrimination of all sounds, including music. However, in two such patients music perception was spared and in one patient music perception was enhanced. The medical literature reports of 33 patients diagnosed with an exclusive deficit for the discrimination and recognition of musical segments (i.e., amusia). The damage in all these cases was localized to the right hemisphere or was bilateral. (with the exception of one case.) The damage in these cases tended to focus around the temporal pole. Consistently, removal of the anterior temporal lobe was also associated with loss of music perception, and recordings directly from the anterior auditory cortex revealed that in both hemispheres, music is perceived medially to speech. These findings therefore imply that the loss of music perception in auditory agnosia is because of damage to the medial anterior STG. In contrast to the association of amusia specific to recognition of melodies (amelodia) with the temporal pole, posterior STG damage was associated with loss of rhythm perception (arryhthmia). Conversely, in two patients rhythm perception was intact, while recognition/discrimination of musical segments was impaired. Amusia also dissociates in regard to enjoyment from music. In two reports, amusic patients, who weren't able to distinguish musical instruments, reported that they still enjoy listening to music. On the other hand, a patient with left hemispheric damage in the amygdala was reported to perceive, but not enjoy, music.

Word meaning deafness / associative auditory agnosia

In 1928, Kleist suggested that the etiology of word deafness could be due either to impaired perception of the sound (apperceptive auditory agnosia), or to impaired extraction of meaning from a sound (associative auditory agnosia). This hypothesis was first tested by Vignolo et al (1969), who examined unilateral stroke patients. They reported that patients with left hemisphere damage were impaired in matching environmental sounds with their corresponding pictures, whereas patients with right hemisphere damage were impaired in the discrimination of meaningless noise segments. The researchers then concluded that left hemispheric damage results in associative auditory agnosia, and right hemisphere damage results in apperceptive auditory agnosia. Although the conclusion reached by this study could be considered over-reaching, associative auditory agnosia could correspond with the disorder word meaning deafness.

Patients with word meaning deafness are characterized by impaired speech recognition but intact repetition of speech and left hemisphere damage. These patients often repeat words in an attempt to extract its meaning (e.g., "Jar....Jar....what is a jar?"). In the first documented case, Bramwell (1897 - translated by Ellis, 1984) reported a patient, who in order to comprehend speech wrote what she heard and then read her own handwriting. Kohn and Friedman, and Symonds also reported word meaning deafness patients who are able to write to dictation. In at least 12 cases, patients with symptoms that correspond with word meaning deafness were diagnosed as auditory agnosia. Unlike most auditory agnosia patients, word meaning deafness patients are not impaired at discriminating gaps of click sounds. It is yet unclear whether word meaning deafness is also synonymous with the disorder deep dysphasia, in which patients cannot repeat nonsense words and produce semantic paraphasia during repetition of real words. Word meaning deafness is also often confused with transcortical sensory aphasia, but such patients differ from the latter by their ability to express themselves appropriately orally or in writing.

Neurological mechanism

Auditory agnosia (with the exception of non-verbal auditory agnosia and amusia) is strongly dependent on damage to both hemispheres. The order of hemispheric damage is irrelevant to manifestation of symptoms, and years could take between the damage of the first hemisphere and the second hemisphere (after which the symptoms suddenly emerge). A study that compared lesion locations, reported that in all cases with bilateral hemispheric damage, at least in one side the lesion included Heschl's gyrus or its underlying white matter. A rare insight into the etiology of this disorder was reported in a study of an auditory agnosia patient with damage to the brainstem, instead of cortex. fMRI scanning of the patient revealed weak activation of the anterior Heschl's gyrus (area R) and anterior superior temporal gyrus. These brain areas are part of the auditory 'what' pathway, and are known from both human and monkey research to participate in the recognition of sounds.

Parsing

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Parsing

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term parsing comes from Latin pars (orationis), meaning part (of speech).

The term has slightly different meanings in different branches of linguistics and computer science. Traditional sentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as sentence diagrams. It usually emphasizes the importance of grammatical divisions such as subject and predicate.

Within computational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a parse tree showing their syntactic relation to each other, which may also contain semantic information. Some parsing algorithms may generate a parse forest or list of parse trees for a syntactically ambiguous input.

The term is also used in psycholinguistics when describing language comprehension. In this context, parsing refers to the way that human beings analyze a sentence or phrase (in spoken language or text) "in terms of grammatical constituents, identifying the parts of speech, syntactic relations, etc." This term is especially common when discussing which linguistic cues help speakers interpret garden-path sentences.

Within computer science, the term is used in the analysis of computer languages, referring to the syntactic analysis of the input code into its component parts in order to facilitate the writing of compilers and interpreters. The term may also be used to describe a split or separation.

Human languages

Main category: Natural language parsing

Traditional methods

The traditional grammatical exercise of parsing, sometimes known as clause analysis, involves breaking down a text into its component parts of speech with an explanation of the form, function, and syntactic relationship of each part. This is determined in large part from study of the language's conjugations and declensions, which can be quite intricate for heavily inflected languages. To parse a phrase such as "man bites dog" involves noting that the singular noun "man" is the subject of the sentence, the verb "bites" is the third person singular of the present tense of the verb "to bite", and the singular noun "dog" is the object of the sentence. Techniques such as sentence diagrams are sometimes used to indicate relation between elements in the sentence.

Parsing was formerly central to the teaching of grammar throughout the English-speaking world, and widely regarded as basic to the use and understanding of written language. However, the general teaching of such techniques is no longer current.

Computational methods

Main article: Syntactic parsing (computational linguistics)

In some machine translation and natural language processing systems, written texts in human languages are parsed by computer programs. Human sentences are not easily parsed by programs, as there is substantial ambiguity in the structure of human language, whose usage is to convey meaning (or semantics) amongst a potentially unlimited range of possibilities, but only some of which are germane to the particular case. So an utterance "Man bites dog" versus "Dog bites man" is definite on one detail but in another language might appear as "Man dog bites" with a reliance on the larger context to distinguish between those two possibilities, if indeed that difference was of concern. It is difficult to prepare formal rules to describe informal behaviour even though it is clear that some rules are being followed.

In order to parse natural language data, researchers must first agree on the grammar to be used. The choice of syntax is affected by both linguistic and computational concerns; for instance some parsing systems use lexical functional grammar, but in general, parsing for grammars of this type is known to be NP-complete. Head-driven phrase structure grammar is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn Treebank. Shallow parsing aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is dependency grammar parsing.

Most modern parsers are at least partly statistical; that is, they rely on a corpus of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. (See machine learning.) Approaches which have been used include straightforward PCFGs (probabilistic context-free grammars), maximum entropy, and neural nets. Most of the more successful systems use lexical statistics (that is, they consider the identities of the words involved, as well as their part of speech). However such systems are vulnerable to overfitting and require some kind of smoothing to be effective.

Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually designed grammars for programming languages. As mentioned earlier some grammar formalisms are very difficult to parse computationally; in general, even if the desired structure is not context-free, some kind of context-free approximation to the grammar is used to perform a first pass. Algorithms which use context-free grammars often rely on some variant of the CYK algorithm, usually with some heuristic to prune away unlikely analyses to save time. (See chart parsing.) However some systems trade speed for accuracy using, e.g., linear-time versions of the shift-reduce algorithm. A somewhat recent development has been parse reranking in which the parser proposes some large number of analyses, and a more complex system selects the best option. In natural language understanding applications, semantic parsers convert the text into a representation of its meaning.

Psycholinguistics

In psycholinguistics, parsing involves not just the assignment of words to categories (formation of ontological insights), but the evaluation of the meaning of a sentence according to the rules of syntax drawn by inferences made from each word in the sentence (known as connotation). This normally occurs as words are being heard or read.

Neurolinguistics generally understands parsing to be a function of working memory, meaning that parsing is used to keep several parts of one sentence at play in the mind at one time, all readily accessible to be analyzed as needed. Because the human working memory has limitations, so does the function of sentence parsing. This is evidenced by several different types of syntactically complex sentences that propose potentially issues for mental parsing of sentences.

The first, and perhaps most well-known, type of sentence that challenges parsing ability is the garden-path sentence. These sentences are designed so that the most common interpretation of the sentence appears grammatically faulty, but upon further inspection, these sentences are grammatically sound. Garden-path sentences are difficult to parse because they contain a phrase or a word with more than one meaning, often their most typical meaning being a different part of speech. For example, in the sentence,” the horse raced past the barn fell”, raced is initially interpreted as a past tense verb, but in this sentence, it functions as part of an adjective phrase. Since parsing is used to identify parts of speech, these sentences challenge the parsing ability of the reader.

Another type of sentence that is difficult to parse is an attachment ambiguity, which includes a phrase that could potentially modify different parts of a sentence, and therefore presents a challenge in identifying syntactic relationship (i.e. “The boy saw the lady with the telescope”, in which the ambiguous phrase with the telescope could modify the boy saw or the lady.) 

A third type of sentence that challenges parsing ability is center embedding, in which phrases are placed in the center of other similarly formed phrases (i.e. “The rat the cat the man hit chased ran into the trap”.) Sentences with 2 or in the most extreme cases 3 center embeddings are challenging for mental parsing, again because of ambiguity of syntactic relationship. 

Within neurolinguistics there are multiple theories that aim to describe how parsing takes place in the brain. One such model is a more traditional generative model of sentence processing, which theorizes that within the brain there is a distinct module designed for sentence parsing, which is preceded by access to lexical recognition and retrieval, and then followed by syntactic processing that considers a single syntactic result of the parsing, only returning to revise that syntactic interpretation if a potential problem is detected. The opposing, more contemporary model theorizes that within the mind, the processing of a sentence is not modular, or happening in strict sequence. Rather, it poses that several different syntactic possibilities can be considered at the same time, because lexical access, syntactic processing, and determination of meaning occur in parallel in the brain. In this way these processes are integrated. 

Although there is still much to learn about the neurology of parsing, studies have shown evidence that several areas of the brain might play a role in parsing. These include the left anterior temporal pole, the left inferior frontal gyrus, the left superior temporal gyrus, the left superior frontal gyrus, the right posterior cingulate cortex, and the left angular gyrus. Although it has not been absolutely proven, it has been suggested that these different structures might favor either phrase-structure parsing or dependency-structure parsing, meaning different types of parsing could be processed in different ways which have yet to be understood. 

Discourse analysis

Discourse analysis examines ways to analyze language use and semiotic events. Persuasive language may be called rhetoric.

Computer languages

Parser

"Parser" redirects here. For the scripting language named Parser, see Parser (programming language).

A parser is a software component that takes input data (frequently text) and builds a data structure – often some kind of parse tree, abstract syntax tree or other hierarchical structure, giving a structural representation of the input while checking for correct syntax. The parsing may be preceded or followed by other steps, or these may be combined into a single step. The parser is often preceded by a separate lexical analyser, which creates tokens from the sequence of input characters; alternatively, these can be combined in scannerless parsing. Parsers may be programmed by hand or may be automatically or semi-automatically generated by a parser generator. Parsing is complementary to templating, which produces formatted output. These may be applied to different domains, but often appear together, such as the scanf/printf pair, or the input (front end parsing) and output (back end code generation) stages of a compiler.

The input to a parser is often text in some computer language, but may also be text in a natural language or less structured textual data, in which case generally only certain parts of the text are extracted, rather than a parse tree being constructed. Parsers range from very simple functions such as scanf, to complex programs such as the frontend of a C++ compiler or the HTML parser of a web browser. An important class of simple parsing is done using regular expressions, in which a group of regular expressions defines a regular language and a regular expression engine automatically generating a parser for that language, allowing pattern matching and extraction of text. In other contexts regular expressions are instead used prior to parsing, as the lexing step whose output is then used by the parser.

The use of parsers varies by input. In the case of data languages, a parser is often found as the file reading facility of a program, such as reading in HTML or XML text; these examples are markup languages. In the case of programming languages, a parser is a component of a compiler or interpreter, which parses the source code of a computer programming language to create some form of internal representation; the parser is a key step in the compiler frontend. Programming languages tend to be specified in terms of a deterministic context-free grammar because fast and efficient parsers can be written for them. For compilers, the parsing itself can be done in one pass or multiple passes – see one-pass compiler and multi-pass compiler.

The implied disadvantages of a one-pass compiler can largely be overcome by adding fix-ups, where provision is made for code relocation during the forward pass, and the fix-ups are applied backwards when the current program segment has been recognized as having been completed. An example where such a fix-up mechanism would be useful would be a forward GOTO statement, where the target of the GOTO is unknown until the program segment is completed. In this case, the application of the fix-up would be delayed until the target of the GOTO was recognized. Conversely, a backward GOTO does not require a fix-up, as the location will already be known.

Context-free grammars are limited in the extent to which they can express all of the requirements of a language. Informally, the reason is that the memory of such a language is limited. The grammar cannot remember the presence of a construct over an arbitrarily long input; this is necessary for a language in which, for example, a name must be declared before it may be referenced. More powerful grammars that can express this constraint, however, cannot be parsed efficiently. Thus, it is a common strategy to create a relaxed parser for a context-free grammar which accepts a superset of the desired language constructs (that is, it accepts some invalid constructs); later, the unwanted constructs can be filtered out at the semantic analysis (contextual analysis) step.

For example, in Python the following is syntactically valid code:

x = 1;
print(x);

The following code, however, is syntactically valid in terms of the context-free grammar, yielding a syntax tree with the same structure as the previous, but violates the semantic rule requiring variables to be initialized before use:

x = 1
print(y)

Overview of process

The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.

The first stage is the token generation, or lexical analysis, by which the input character stream is split into meaningful symbols defined by a grammar of regular expressions. For example, a calculator program would look at an input such as "12 * (3 + 4)^2" and split it into the tokens 12, *, (, 3, +, 4, ), ^, 2, each of which is a meaningful symbol in the context of an arithmetic expression. The lexer would contain rules to tell it that the characters *, +, ^, ( and ) mark the start of a new token, so meaningless tokens like "12*" or "(3" will not be generated.

The next stage is parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a context-free grammar which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with attribute grammars.

The final phase is semantic parsing or analysis, which is working out the implications of the expression just validated and taking the appropriate action. In the case of a calculator or interpreter, the action is to evaluate the expression or program; a compiler, on the other hand, would generate some kind of code. Attribute grammars can also be used to define these actions.

Types of parsers

The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:

Top-down parsing

Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse trees using a top-down expansion of the given formal grammar rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules. This is known as the primordial soup approach. Very similar to sentence diagramming, primordial soup breaks down the constituencies of sentences.

Bottom-up parsing

A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.

LL parsers and recursive-descent parser are examples of top-down parsers that cannot accommodate left recursive production rules. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsing ambiguous context-free grammars, more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan which accommodate ambiguity and left recursion in polynomial time and which generate polynomial-size representations of the potentially exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a given context-free grammar.

An important distinction with regard to parsers is whether a parser generates a leftmost derivation or a rightmost derivation (see context-free grammar). LL parsers will generate a leftmost derivation and LR parsers will generate a rightmost derivation (although usually in reverse).

Some graphical parsing algorithms have been designed for visual programming languages. Parsers for visual languages are sometimes based on graph grammars.

Adaptive parsing algorithms have been used to construct "self-extending" natural language user interfaces.

Implementation

The simplest parser APIs read the entire input file, do some intermediate computation, and then write the entire output file. (Such as in-memory multi-pass compilers).

Those simple parsers won't work when there isn't enough memory to store the entire input file or the entire output file. They also won't work for never-ending streams of data from the real world.

Some alternative API approaches for parsing such data:

• push parsers that call the registered handlers (callbacks) as soon as the parser detects relevant tokens in the input stream (such as Expat)
• pull parsers
• incremental parsers (such as incremental chart parsers) that, as the text of the file is edited by a user, does not need to completely re-parse the entire file.
• Active vs passive parsers

Parser development software

See also: Comparison of parser generators

Some of the well known parser development tools include the following:

• ANTLR
• Bison
• Coco/R
• Definite clause grammar
• GOLD
• JavaCC
• Lemon
• Lex
• LuZc
• Parboiled
• Parsec
• Ragel
• Spirit Parser Framework
• Syntax Definition Formalism
• SYNTAX
• XPL
• Yacc
• PackCC

Lookahead

C program that cannot be parsed with less than 2 token lookahead. Top: C grammar excerpt. Bottom: a parser has digested the tokens "int v;main(){" and is about to choose a rule to derive Stmt. Looking only at the first lookahead token "v", it cannot decide which of both alternatives for Stmt to choose; the latter requires peeking at the second token.

Lookahead establishes the maximum incoming tokens that a parser can use to decide which rule it should use. Lookahead is especially relevant to LL, LR, and LALR parsers, where it is often explicitly indicated by affixing the lookahead to the algorithm name in parentheses, such as LALR(1).

Most programming languages, the primary target of parsers, are carefully defined in such a way that a parser with limited lookahead, typically one, can parse them, because parsers with limited lookahead are often more efficient. One important change to this trend came in 1990 when Terence Parr created ANTLR for his Ph.D. thesis, a parser generator for efficient LL(k) parsers, where k is any fixed value.

LR parsers typically have only a few actions after seeing each token. They are shift (add this token to the stack for later reduction), reduce (pop tokens from the stack and form a syntactic construct), end, error (no known rule applies) or conflict (does not know whether to shift or reduce).

Lookahead has two advantages.

• It helps the parser take the correct action in case of conflicts. For example, parsing the if statement in the case of an else clause.
• It eliminates many duplicate states and eases the burden of an extra stack. A C language non-lookahead parser will have around 10,000 states. A lookahead parser will have around 300 states.

Example: Parsing the Expression 1 + 2 * 3

Set of expression parsing rules (called grammar) is as follows,
Rule1:	E → E + E	Expression is the sum of two expressions.
Rule2:	E → E * E	Expression is the product of two expressions.
Rule3:	E → number	Expression is a simple number
Rule4:	+ has less precedence than *

Most programming languages (except for a few such as APL and Smalltalk) and algebraic formulas give higher precedence to multiplication than addition, in which case the correct interpretation of the example above is 1 + (2 * 3). Note that Rule4 above is a semantic rule. It is possible to rewrite the grammar to incorporate this into the syntax. However, not all such rules can be translated into syntax.

Simple non-lookahead parser actions

Initially Input = [1, +, 2, *, 3]

1. Shift "1" onto stack from input (in anticipation of rule3). Input = [+, 2, *, 3] Stack = [1]
2. Reduces "1" to expression "E" based on rule3. Stack = [E]
3. Shift "+" onto stack from input (in anticipation of rule1). Input = [2, *, 3] Stack = [E, +]
4. Shift "2" onto stack from input (in anticipation of rule3). Input = [*, 3] Stack = [E, +, 2]
5. Reduce stack element "2" to Expression "E" based on rule3. Stack = [E, +, E]
6. Reduce stack items [E, +, E] and new input "E" to "E" based on rule1. Stack = [E]
7. Shift "*" onto stack from input (in anticipation of rule2). Input = [3] Stack = [E,*]
8. Shift "3" onto stack from input (in anticipation of rule3). Input = [] (empty) Stack = [E, *, 3]
9. Reduce stack element "3" to expression "E" based on rule3. Stack = [E, *, E]
10. Reduce stack items [E, *, E] and new input "E" to "E" based on rule2. Stack = [E]

The parse tree and resulting code from it is not correct according to language semantics.

To correctly parse without lookahead, there are three solutions:

• The user has to enclose expressions within parentheses. This often is not a viable solution.
• The parser needs to have more logic to backtrack and retry whenever a rule is violated or not complete. The similar method is followed in LL parsers.
• Alternatively, the parser or grammar needs to have extra logic to delay reduction and reduce only when it is absolutely sure which rule to reduce first. This method is used in LR parsers. This correctly parses the expression but with many more states and increased stack depth.

Lookahead parser actions

1. Shift 1 onto stack on input 1 in anticipation of rule3. It does not reduce immediately.
2. Reduce stack item 1 to simple Expression on input + based on rule3. The lookahead is +, so we are on path to E +, so we can reduce the stack to E.
3. Shift + onto stack on input + in anticipation of rule1.
4. Shift 2 onto stack on input 2 in anticipation of rule3.
5. Reduce stack item 2 to Expression on input * based on rule3. The lookahead * expects only E before it.
6. Now stack has E + E and still the input is *. It has two choices now, either to shift based on rule2 or reduction based on rule1. Since * has higher precedence than + based on rule4, we shift * onto stack in anticipation of rule2.
7. Shift 3 onto stack on input 3 in anticipation of rule3.
8. Reduce stack item 3 to Expression after seeing end of input based on rule3.
9. Reduce stack items E * E to E based on rule2.
10. Reduce stack items E + E to E based on rule1.

The parse tree generated is correct and simply more efficient than non-lookahead parsers. This is the strategy followed in LALR parsers.

Generative grammar

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Generative_grammar 

A generative parse tree: the sentence is divided into a noun phrase (subject), and a verb phrase which includes the object. This is in contrast to structural and functional grammar which consider the subject and object as equal constituents.

Generative grammar, or generativism /ˈdʒɛnərətɪvɪzəm/, is a linguistic theory that regards linguistics as the study of a hypothesised innate grammatical structure. It is a biological or biologistic modification of earlier structuralist theories of linguistics, deriving from logical syntax and glossematics. Generative grammar considers grammar as a system of rules that generates exactly those combinations of words that form grammatical sentences in a given language. It is a system of explicit rules that may apply repeatedly to generate an indefinite number of sentences which can be as long as one wants them to be. The difference from structural and functional models is that the object is base-generated within the verb phrase in generative grammar. This purportedly cognitive structure is thought of as being a part of a universal grammar, a syntactic structure which is caused by a genetic mutation in humans.

Generativists have created numerous theories to make the NP VP (NP) analysis work in natural language description. That is, the subject and the verb phrase appearing as independent constituents, and the object placed within the verb phrase. A main point of interest remains in how to appropriately analyse Wh-movement and other cases where the subject appears to separate the verb from the object. Although claimed by generativists as a cognitively real structure, neuroscience has found no evidence for it. In other words, generative grammar encompasses proposed models of linguistic cognition; but there is still no specific indication that these are quite correct. Recent arguments have been made that the success of large language models undermine key claims of generative syntax because they are based on markedly different assumptions, including gradient probability and memorized constructions, and out-perform generative theories both in syntactic structure and in integration with cognition and neuroscience.

Frameworks

There are a number of different approaches to generative grammar. Common to all is the effort to come up with a set of rules or principles that formally defines each and every one of the members of the set of well-formed expressions of a natural language. The term generative grammar has been associated with at least the following schools of linguistics:

• Transformational grammar (TG)
  • Standard theory (ST)
  • Extended standard theory (EST)
  • Revised extended standard theory (REST)
  • Principles and parameters theory (P&P)
    • Government and binding theory (GB)
    • Minimalist program (MP)
• Monostratal (or non-transformational) grammars
  • Relational grammar (RG)
  • Lexical-functional grammar (LFG)
  • Generalized phrase structure grammar (GPSG)
  • Head-driven phrase structure grammar (HPSG)
  • Categorial grammar
  • Tree-adjoining grammar
  • Optimality Theory (OT)

Historical development of models of transformational grammar

Main article: Transformational grammar

Leonard Bloomfield, an influential linguist in the American Structuralist tradition, saw the ancient Indian grammarian Pāṇini as an antecedent of structuralism. However, in Aspects of the Theory of Syntax, Chomsky writes that "even Panini's grammar can be interpreted as a fragment of such a 'generative grammar'", a view that he reiterated in an award acceptance speech delivered in India in 2001, where he claimed that "the first 'generative grammar' in something like the modern sense is Panini's grammar of Sanskrit".

Military funding to generativist research was influential to its early success in the 1960s.

Generative grammar has been under development since the mid 1950s, and has undergone many changes in the types of rules and representations that are used to predict grammaticality. In tracing the historical development of ideas within generative grammar, it is useful to refer to the various stages in the development of the theory:

Standard theory (1956–1965)

The so-called standard theory corresponds to the original model of generative grammar laid out by Chomsky in 1965.

A core aspect of standard theory is the distinction between two different representations of a sentence, called deep structure and surface structure. The two representations are linked to each other by transformational grammar.

Extended standard theory (1965–1973)

The so-called extended standard theory was formulated in the late 1960s and early 1970s. Features are:

• syntactic constraints
• generalized phrase structures (X-bar theory)

Revised extended standard theory (1973–1976)

The so-called revised extended standard theory was formulated between 1973 and 1976. It contains

• restrictions upon X-bar theory (Jackendoff (1977)).
• assumption of the complementizer position.
• Move α

Relational grammar (ca. 1975–1990)

Main article: Relational grammar

An alternative model of syntax based on the idea that notions like subject, direct object, and indirect object play a primary role in grammar.

Government and binding/principles and parameters theory (1981–1990)

Main articles: Government and binding and Principles and parameters

Chomsky's Lectures on Government and Binding (1981) and Barriers (1986).

Minimalist program (1990–present)

Main article: Minimalist program

The minimalist program is a line of inquiry that hypothesizes that the human language faculty is optimal, containing only what is necessary to meet humans' physical and communicative needs, and seeks to identify the necessary properties of such a system. It was proposed by Chomsky in 1993.

Context-free grammars

Main article: Context-free grammar

Generative grammars can be described and compared with the aid of the Chomsky hierarchy (proposed by Chomsky in the 1950s). This sets out a series of types of formal grammars with increasing expressive power. Among the simplest types are the regular grammars (type 3); Chomsky argues that these are not adequate as models for human language, because of the allowance of the center-embedding of strings within strings, in all natural human languages.

At a higher level of complexity are the context-free grammars (type 2). The derivation of a sentence by such a grammar can be depicted as a derivation tree. Linguists working within generative grammar often view such trees as a primary object of study. According to this view, a sentence is not merely a string of words. Instead, adjacent words are combined into constituents, which can then be further combined with other words or constituents to create a hierarchical tree-structure.

The derivation of a simple tree-structure for the sentence "the dog ate the bone" proceeds as follows. The determiner the and noun dog combine to create the noun phrase the dog. A second noun phrase the bone is created with determiner the and noun bone. The verb ate combines with the second noun phrase, the bone, to create the verb phrase ate the bone. Finally, the first noun phrase, the dog, combines with the verb phrase, ate the bone, to complete the sentence: the dog ate the bone. The following tree diagram illustrates this derivation and the resulting structure:

Such a tree diagram is also called a phrase marker. They can be represented more conveniently in text form, (though the result is less easy to read); in this format the above sentence would be rendered as:
[_S [_NP [_D The ] [_N dog ] ] [_VP [_V ate ] [_NP [_D the ] [_N bone ] ] ] ]

Chomsky has argued that phrase structure grammars are also inadequate for describing natural languages, and formulated the more complex system of transformational grammar.

Evidentiality

Noam Chomsky, the main proponent of generative grammar, believed he had found linguistic evidence that syntactic structures are not learned but "acquired" by the child from universal grammar. This led to the establishment of the poverty of the stimulus argument in the 1980s. However, critics claimed Chomsky's linguistic analysis had been inadequate. Linguistic studies had been made to prove that children have innate knowledge of grammar that they could not have learned. For example, it was shown that a child acquiring English knows how to differentiate between the place of the verb in main clauses from the place of the verb in relative clauses. In the experiment, children were asked to turn a declarative sentence with a relative clause into an interrogative sentence. Against the expectations of the researchers, the children did not move the verb in the relative clause to its sentence initial position, but to the main clause initial position, as is grammatical. Critics however pointed out that this was not evidence for the poverty of the stimulus because the underlying structures that children were proved to be able to manipulate were actually highly common in children's literature and everyday language. This led to a heated debate which resulted in the rejection of generative grammar from mainstream psycholinguistics and applied linguistics around 2000. In the aftermath, some professionals argued that decades of research had been wasted due to generative grammar, an approach which has failed to make a lasting impact on the field.

The sentence from the study which shows that it is not the verb in the relative clause, but the verb in the main clause that raises to the head C°.

There is no evidence that syntactic structures are innate. While some hopes were raised at the discovery of the FOXP2 gene, there is not enough support for the idea that it is 'the grammar gene' or that it had much to do with the relatively recent emergence of syntactical speech.

Neuroscientific studies using ERPs have found no scientific evidence for the claim that human mind processes grammatical objects as if they were placed inside the verb phrase. Instead, brain research has shown that sentence processing is based on the interaction of semantic and syntactic processing. However, since generative grammar is not a theory of neurology, but a theory of psychology, it is completely normal in the field of neurology to find no concreteness of the verb phrase in the brain. In fact, these rules do not exist in our brains, but they do model the external behaviour of the mind. This is why GG claims to be a theory of psychology and is considered to be real cognitively.

Generativists also claim that language is placed inside its own mind module and that there is no interaction between first-language processing and other types of information processing, such as mathematics. This claim is not based on research or the general scientific understanding of how the brain works.

Chomsky has answered the criticism by emphasising that his theories are actually counter-evidential. He however believes it to be a case where the real value of the research is only understood later on, as it was with Galileo.

Music

Generative grammar has been used in music theory and analysis since the 1980s. The most well-known approaches were developed by Mark Steedman as well as Fred Lerdahl and Ray Jackendoff, who formalized and extended ideas from Schenkerian analysis. More recently, such early generative approaches to music were further developed and extended by various scholars. French composer Philippe Manoury applied the systematic of generative grammar to the field of contemporary classical music.

Algorithmic composition

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Algorithmic_composition

Algorithmic composition is the technique of using algorithms to create music.

Algorithms (or, at the very least, formal sets of rules) have been used to compose music for centuries; the procedures used to plot voice-leading in Western counterpoint, for example, can often be reduced to algorithmic determinacy. The term can be used to describe music-generating techniques that run without ongoing human intervention, for example through the introduction of chance procedures. However through live coding and other interactive interfaces, a fully human-centric approach to algorithmic composition is possible.

Some algorithms or data that have no immediate musical relevance are used by composers as creative inspiration for their music. Algorithms such as fractals, L-systems, statistical models, and even arbitrary data (e.g. census figures, GIS coordinates, or magnetic field measurements) have been used as source materials.

Models for algorithmic composition

Compositional algorithms are usually classified by the specific programming techniques they use. The results of the process can then be divided into 1) music composed by computer and 2) music composed with the aid of computer. Music may be considered composed by computer when the algorithm is able to make choices of its own during the creation process.

Another way to sort compositional algorithms is to examine the results of their compositional processes. Algorithms can either 1) provide notational information (sheet music or MIDI) for other instruments or 2) provide an independent way of sound synthesis (playing the composition by itself). There are also algorithms creating both notational data and sound synthesis.

One way to categorize compositional algorithms is by their structure and the way of processing data, as seen in this model of six partly overlapping types:

• translational models
• mathematical models
• knowledge-based systems
• grammars
• optimization approaches
• evolutionary methods
• systems which learn
• hybrid systems

Translational models

This is an approach to music synthesis that involves "translating" information from an existing non-musical medium into a new sound. The translation can be either rule-based or stochastic. For example, when translating a picture into sound, a JPEG image of a horizontal line may be interpreted in sound as a constant pitch, while an upwards-slanted line may be an ascending scale. Oftentimes, the software seeks to extract concepts or metaphors from the medium, (such as height or sentiment) and apply the extracted information to generate songs using the ways music theory typically represents those concepts. Another example is the translation of text into music, which can approach composition by extracting sentiment (positive or negative) from the text using machine learning methods like sentiment analysis and represents that sentiment in terms of chord quality such as minor (sad) or major (happy) chords in the musical output generated.

Mathematical models

Mathematical models are based on mathematical equations and random events. The most common way to create compositions through mathematics is stochastic processes. In stochastic models a piece of music is composed as a result of non-deterministic methods. The compositional process is only partially controlled by the composer by weighting the possibilities of random events. Prominent examples of stochastic algorithms are Markov chains and various uses of Gaussian distributions. Stochastic algorithms are often used together with other algorithms in various decision-making processes.

Music has also been composed through natural phenomena. These chaotic models create compositions from the harmonic and inharmonic phenomena of nature. For example, since the 1970s fractals have been studied also as models for algorithmic composition.

As an example of deterministic compositions through mathematical models, the On-Line Encyclopedia of Integer Sequences provides an option to play an integer sequence as 12-tone equal temperament music. (It is initially set to convert each integer to a note on an 88-key musical keyboard by computing the integer modulo 88, at a steady rhythm. Thus 123456, the natural numbers, equals half of a chromatic scale.) As another example, the all-interval series has been used for computer-aided composition. 

Knowledge-based systems

One way to create compositions is to isolate the aesthetic code of a certain musical genre and use this code to create new similar compositions. Knowledge-based systems are based on a pre-made set of arguments that can be used to compose new works of the same style or genre. Usually this is accomplished by a set of tests or rules requiring fulfillment for the composition to be complete.

Grammars

Music can also be examined as a language with a distinctive grammar set. Compositions are created by first constructing a musical grammar, which is then used to create comprehensible musical pieces. Grammars often include rules for macro-level composing, for instance harmonies and rhythm, rather than single notes.

Optimization approaches

When generating well defined styles, music can be seen as a combinatorial optimization problem, whereby the aim is to find the right combination of notes such that the objective function is minimized. This objective function typically contains rules of a particular style, but could be learned using machine learning methods such as Markov models. Researchers have generated music using a myriad of different optimization methods, including integer programming, variable neighbourhood search, and evolutionary methods as mentioned in the next subsection.

Evolutionary methods

Evolutionary methods of composing music are based on genetic algorithms. The composition is being built by the means of evolutionary process. Through mutation and natural selection, different solutions evolve towards a suitable musical piece. Iterative action of the algorithm cuts out bad solutions and creates new ones from those surviving the process. The results of the process are supervised by the critic, a vital part of the algorithm controlling the quality of created compositions.

Evo-Devo approach

Evolutionary methods, combined with developmental processes, constitute the evo-devo approach for generation and optimization of complex structures. These methods have also been applied to music composition, where the musical structure is obtained by an iterative process that transform a very simple composition (made of a few notes) into a complex fully-fledged piece (be it a score, or a MIDI file).

Systems that learn

Further information: Machine improvisation, Machine listening, and Machine learning

Learning systems are programs that have no given knowledge of the genre of music they are working with. Instead, they collect the learning material by themselves from the example material supplied by the user or programmer. The material is then processed into a piece of music similar to the example material. This method of algorithmic composition is strongly linked to algorithmic modeling of style, machine improvisation, and such studies as cognitive science and the study of neural networks. Assayag and Dubnov proposed a variable length Markov model to learn motif and phrase continuations of different length. Marchini and Purwins presented a system that learns the structure of an audio recording of a rhythmical percussion fragment using unsupervised clustering and variable length Markov chains and that synthesizes musical variations from it.

Hybrid systems

Programs based on a single algorithmic model rarely succeed in creating aesthetically satisfying results. For that reason algorithms of different type are often used together to combine the strengths and diminish the weaknesses of these algorithms. Creating hybrid systems for music composition has opened up the field of algorithmic composition and created also many brand new ways to construct compositions algorithmically. The only major problem with hybrid systems is their growing complexity and the need of resources to combine and test these algorithms.

Another approach, which can be called computer-assisted composition, is to algorithmically create certain structures for finally "hand-made" compositions. As early as in the 1960s, Gottfried Michael Koenig developed computer programs Project 1 and Project 2 for aleatoric music, the output of which was sensibly structured "manually" by means of performance instructions. In the 2000s, Andranik Tangian developed a computer algorithm to determine the time event structures for rhythmic canons and rhythmic fugues, which were then worked out into harmonic compositions Eine kleine Mathmusik I and Eine kleine Mathmusik II; for scores and recordings see.