The Evolution of Complexity - Abstracts. The Evolution of Complexity - Abstracts. By Robert Glück
This contribution investigates the manipulation of formal language hierarchies, a prerequisite for overcoming the computational complexity of linguistic modeling [7]. We derive the basic tasks for metacomputation by a systematic analysis of language hierarchies and show that in order to fully support formal linguistic modeling in the computer the following transformation have to be performed effectively and efficiently: flattening translator and interpreter hierarchies, converting translators into interpreters and vice versa.
It is surprising, that only one case (3a), the conversion of interpreters into translators, has been studied in computer science [1,6]. We argue that the full variety of language hierarchies should be considered in order to achieve the full flexibility of linguistic modeling. We hope that this exposition contributes to a systematic understanding of linguistic modeling both in cybernetics and computer science. It is a continuation of our work on metacomputation [2-5], inspired by Turchin's pioneering works [7,8].
One of the defining features of modern science is the use of linguistic models [7]. Computer science is laying the foundations and developing the research paradigm and scientific methods for the exploration of formal linguistic modeling. Modeling by means of formal language usually involves the creation of language hierarchies [9].
The goal of metacomputation (see e.g. [8,4]) is to derive new, more compact language definitions from arbitrary linguistic hierarchies. Let us denote the process of performing metacomputation by Mc. In order to express that Mc is one level higher than ordinary computation, we will move the metacomputed expression downwards (see below).
We know of exactly two forms of linguistic definitions: (i) a translator, say Transi, of messages from one language, say Li, to another language, say Li-1: <Transi msgi> => msgi-1; (ii) an interpreter, say Inti, of messages from one language, say Li, directly through actions in another language, say Li-1: <Inti (msgi, in)> => out. Each level in a hierarchy is either translative or interpretive.
We distinguish four cases of metacomputation of language hierarchies.
1. Translator hierarchy. The goal of metacomputation is to derive a new translator Trans by composition of the translators Trans1 ... Transn, where Trans is a translator from Ln to L0.
<Mc _______________________________________> => Trans
<Trans1 <Trans2 ... <Transn msgn> ...>>
2. Interpreter hierarchy. The goal of metacomputation is to derive a new interpreter Int by multi-level specialization of the interpreters Int1 ... Intn, where Int is an interpreter of Ln in L0.
<Mc _______________________________________________> => Int
<Int1 (Int2, (Int3, ... (Intn, (msgn, in)) ...))>
3. Conversion to dual definition. The goal of metacomputation is the conversion of one form of definition to its dual form.
3a. Converting an interpreter to a translator. 3b. Converting a translator to an interpreter.
4. General language hierarchy. The goal of metacomputation is to convert a mixture of translators and interpreters into one of the two definition forms: a translator or an interpreter.