Computing by only observing

Matteo Cavaliere; Pierluigi Frisco; Hendrik Jan Hoogeboom

doi:10.1007/11779148_28

Computing by only observing

Matteo Cavaliere, Pierluigi Frisco, Hendrik Jan Hoogeboom

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Citations (Scopus)

Abstract

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. © Springer-Verlag Berlin Heidelberg 2006.

Original language	English
Title of host publication	Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings
Pages	304-314
Number of pages	11
Volume	4036 LNCS
DOIs	https://doi.org/10.1007/11779148_28
Publication status	Published - 2006
Event	10th International Conference on Developments in Language Theory - Santa Barbara, CA, United States Duration: 26 Jun 2006 → 29 Jun 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4036 LNCS
ISSN (Print)	0302-9743

Conference

Conference	10th International Conference on Developments in Language Theory
Abbreviated title	DLT 2006
Country/Territory	United States
City	Santa Barbara, CA
Period	26/06/06 → 29/06/06

Access to Document

10.1007/11779148_28

Cite this

Cavaliere, M., Frisco, P., & Hoogeboom, H. J. (2006). Computing by only observing. In Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings (Vol. 4036 LNCS, pp. 304-314). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4036 LNCS). https://doi.org/10.1007/11779148_28

@inproceedings{bfd5e7cc24cf46c39b84c0bc127f2f4d,

title = "Computing by only observing",

abstract = "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. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",

author = "Matteo Cavaliere and Pierluigi Frisco and Hoogeboom, {Hendrik Jan}",

year = "2006",

doi = "10.1007/11779148_28",

language = "English",

isbn = "354035428X",

volume = "4036 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "304--314",

booktitle = "Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings",

note = "10th International Conference on Developments in Language Theory, DLT 2006 ; Conference date: 26-06-2006 Through 29-06-2006",

}

Cavaliere, M, Frisco, P & Hoogeboom, HJ 2006, Computing by only observing. in Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings. vol. 4036 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4036 LNCS, pp. 304-314, 10th International Conference on Developments in Language Theory, Santa Barbara, CA, United States, 26/06/06. https://doi.org/10.1007/11779148_28

Computing by only observing. / Cavaliere, Matteo; Frisco, Pierluigi; Hoogeboom, Hendrik Jan.
Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings. Vol. 4036 LNCS 2006. p. 304-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4036 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Computing by only observing

AU - Cavaliere, Matteo

AU - Frisco, Pierluigi

AU - Hoogeboom, Hendrik Jan

PY - 2006

Y1 - 2006

N2 - 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. © Springer-Verlag Berlin Heidelberg 2006.

AB - 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. © Springer-Verlag Berlin Heidelberg 2006.

UR - http://www.scopus.com/inward/record.url?scp=33746191320&partnerID=8YFLogxK

U2 - 10.1007/11779148_28

DO - 10.1007/11779148_28

M3 - Conference contribution

SN - 354035428X

SN - 9783540354284

VL - 4036 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 304

EP - 314

BT - Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings

T2 - 10th International Conference on Developments in Language Theory

Y2 - 26 June 2006 through 29 June 2006

ER -

Computing by only observing

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this