|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040101,
author = {Carlos Martin-Vide and Gheorghe P\u{a}un},
title = {Cooperating Distributed Splicing Systems},
journal = jalc,
year = 1999,
volume = 4,
number = 1,
pages = {3--16},
keywords = {formal languages, grammar systems, DNA computing,
H systems},
abstract = {We introduce a new class of cooperating distributed
H systems which consist of a given set of splicing systems
(sets of splicing rules plus sets of axioms), similar in
form to the cooperating distributed grammar systems. By
applying iteratively the components of such a system
(starting from a given initial string), in a sequence which
runs nondeterministically, in such a way that a step is
considered correctly finished only if no more splicing is
possible, we obtain a language. Somewhat surprisingly if we
take into account the loose control on the operations we
carry out, a characterization of recursively enumerable
languages is obtained, by mechanisms as above with only
three components. We also characterize the recursively
enumerable languages by cooperating distributed H systems
with the components containing at most three splicing rules
(in this case the number of components is no longer bounded).}
}