Controlled H Systems and Chomsky Hierarchy

Article type: Research Article

Authors: Paun, Gheorghe

Affiliations: Institute of Mathematics of the Romanian Academy, PO Box 1 – 764, 10700 Bucureşti, Romania. E-mail: gpaun@imar.ro

Abstract: This paper is an up-to-dated survey of results about the power of controlled extended H systems of various types. Such systems are finite generative devices based on the splicing operation, which, in turn, is a model of the DNA recombination. When no control is imposed on the splicing operation, we get a characterization of regular languages. When a control is considered, we obtain characterizations of recursively enumerable languages. We briefly discuss here H systems with control mechanisms similar to those in regulated rewriting area in formal language theory. We do not present proofs, but only definitions, results, and bibliographical information. Looking for characterizations of families in Chomsky hierarchy other than those of regular and of recursively enumerable languages, we closely investigate the H systems with permitting context conditions. We disprove a conjecture of Chakaravarthy and Krithivasan: such systems of radius one and using only one-sided context conditions can generate all context-free languages (the conjecture was that a characterization of linear languages is obtained). Some open problems are also mentioned.

DOI: 10.3233/FI-1997-30104

Journal: Fundamenta Informaticae, vol. 30, no. 1, pp. 45-57, 1997