We consider first an operation with strings and languages suggested by superposed windows on the computer screen (as well as by cryptographic systems of Richelieu type): we assume that the strings contain usual symbols as well as a transparent symbol. Superposing two strings (justified to left), we produce a new string consisting of the symbols visible from above. This operation is investigated as an abstract operation on strings, then it is used in building a variant of grammar systems with the component grammars working on the layers of an array of strings. Each grammar can rewrite only symbols in its layer which are visible from above. The language generated in this way consists of strings of the visible symbols, produced at the end of a derivation. The power of several variants of these generative mechanisms is investigated for the case of two layered strings. When a matrix-like control on the work of the component grammars is considered, then a characterization of recursively enumerable languages is obtained.

Grammars Working on Layered Strings / Bottoni, Paolo Gaspare; G., Mauri; P., Mussio; G., Paun. - In: ACTA CYBERNETICA. - ISSN 0324-721X. - STAMPA. - 13:(1998), pp. 339-358.

Grammars Working on Layered Strings

BOTTONI, Paolo Gaspare;
1998

Abstract

We consider first an operation with strings and languages suggested by superposed windows on the computer screen (as well as by cryptographic systems of Richelieu type): we assume that the strings contain usual symbols as well as a transparent symbol. Superposing two strings (justified to left), we produce a new string consisting of the symbols visible from above. This operation is investigated as an abstract operation on strings, then it is used in building a variant of grammar systems with the component grammars working on the layers of an array of strings. Each grammar can rewrite only symbols in its layer which are visible from above. The language generated in this way consists of strings of the visible symbols, produced at the end of a derivation. The power of several variants of these generative mechanisms is investigated for the case of two layered strings. When a matrix-like control on the work of the component grammars is considered, then a characterization of recursively enumerable languages is obtained.
1998
regulated rewriting; grammar systems; visual languages; Chomsky hierarchy
01 Pubblicazione su rivista::01a Articolo in rivista
Grammars Working on Layered Strings / Bottoni, Paolo Gaspare; G., Mauri; P., Mussio; G., Paun. - In: ACTA CYBERNETICA. - ISSN 0324-721X. - STAMPA. - 13:(1998), pp. 339-358.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/47659
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact