The paradigm of evolution/observation is based on the idea that a computing device can be obtained by combining a basic system and an observer that transforms the evolution of the basic system into a readable output. In this framework we investigate what can be computed by changing the observer but not the basic observed system. We consider grammars as basic systems combined with finite state automata as observers, watching either the sequence of sentential forms or the productions used by the grammar. It is possible to obtain computational completeness only varying the observer, without modifying the basic system, which is a fixed context-free grammar.
|Title of host publication||Developments in Language Theory|
|Subtitle of host publication||10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006, Proceedings|
|Publisher||Springer Berlin Heidelberg|
|Number of pages||11|
|Publication status||Published - 2006|