Wyniki wyszukiwania - BazTech

1

On Controlled P Systems

Krithivasan K., Păun G., Ramanujan A.

Fundamenta Informaticae

|

2014

|

Vol. 131, nr 3-4

451--464

EN

We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). A series of open problems and research topics are formulated.

2

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

EN

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.

3

On Characterizing Recursively Enumerable Languages by Insertion Grammars

Mutyam M., Krithivasan K., Reddy A. S.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

317--324

EN

Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages.

4

Contextual P Systems

Krithivasan K., Madhu M.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 1-3

179-189

EN

Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P systems with right-sided erased contexts are computationally complete.