|
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 1 van 1 gevonden artikelen
| Titel: |
Controlled H Systems and Chomsky Hierarchy |
| Auteur: |
Paun, Gheorghe |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 30 (2011) nr. 1 pagina's 45-57 |
| Jaar: |
2011-02-08 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 1 van 1 gevonden artikelen