In this paper we prove that any recursively enumerable language can be generated using a distributed splicing system with a fi xed number of test tubes. This improves a recent result by Csuhaj- Varju, Kari and Paun proving computational completeness only for a system with a number of tubes depending on the cardinality of the used alphabet.
Zandron, C., Ferretti, C., Mauri, G. (1997). A reduced distributed splicing system for RE languages. In Paun G, A. Salomaa (a cura di), New trends in formal languages (pp. 319-329). Berlin : Springer [10.1007/3-540-62844-4_23].
A reduced distributed splicing system for RE languages
ZANDRON, CLAUDIO;FERRETTI, CLAUDIO;MAURI, GIANCARLO
1997
Abstract
In this paper we prove that any recursively enumerable language can be generated using a distributed splicing system with a fi xed number of test tubes. This improves a recent result by Csuhaj- Varju, Kari and Paun proving computational completeness only for a system with a number of tubes depending on the cardinality of the used alphabet.
File in 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.
