Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Modelling DNA and RNA secondary structures using matrix insertion-deletion systems

Kuppusamy L., Mahendran A.

International Journal of Applied Mathematics and Computer Science

2016

Vol. 26, no. 1

245--258

Insertion and deletion are operations that occur commonly in DNA processing and RNA editing. Since biological macromolecules can be viewed as symbols, gene sequences can be represented as strings and structures can be interpreted as languages. This suggests that the bio-molecular structures that occur at different levels can be theoretically studied by formal languages. In the literature, there is no unique grammar formalism that captures various bio-molecular structures. To overcome this deficiency, in this paper, we introduce a simple grammar model called the matrix insertion–deletion system, and using it we model several bio-molecular structures that occur at the intramolecular, intermolecular and RNA secondary levels.

On the Trade-off Between Ambiguity and Complexity in Contextual Languages

Kuppusamy L., Mahendran A., Krithivasan K.

Fundamenta Informaticae

2013

Vol. 122, nr 4

315--326

Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Pǎun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework.