Fundamenta Informaticae - Volume 64, issue 1-4

Authors: Krishna, Shankara Narayanan | Rama, R. | Ramesh, H.

Article Type: Research Article

Abstract: In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.

Keywords: P systems, contextual grammars, replicated rewriting, leftmost rewriting, recursively enumerable languages

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 241-253, 2005

Authors: Kudlek, Manfred

Article Type: Research Article

Abstract: A generalization of contextual grammars by adding probabilities is introduced, enriching the generative power of such grammars. An example exhibits a non-contextual, even not context-free language.

Keywords: Contextual grammar, probabilistic grammar, multiset

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 255-260, 2005

Authors: Manca, Vincenzo

Article Type: Research Article

Abstract: The double stranded structure of DNA molecules is investigated in an abstract setting. Only the general structure of bilinear strings is taken into account regardless of specific physical and biochemical aspects of DNA molecules. In this context, the principles which DNA processes are based on are formulated in an abstract form. Surprisingly enough, some intrinsic features of DNA molecules turn out to be implied by these general principles.

Keywords: DNA structure, bilinearity, complementarity, antiparallelism, DNA helix, DNA computing

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 261-273, 2005

Authors: Mardare, Radu | Priami, Corrado

Article Type: Research Article

Abstract: Our paper proposes a technique for performing logical analysis over the calculi for communication and mobility, i.e., Ambient Calculus type of calculi. We show how this analysis can be used in the case of biological models in order to obtain significant information for biologists. The technique is based on set theoretical models we developed for ambient processes by using the power of Hypersets Theory. These models are further used as possible worlds in a Kripke structure organized for …a propositional branching temporal logic. Providing the temporal logical structure for the accessibility relation between ambient processes, we open the perspective of reusing model checking algorithms developed for temporal logics in analyzing any phenomena that can be described by these calculi. Show more

Keywords: Hypersets, process algebra, ambient calculus, temporal logics, model checking

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 275-289, 2005

Authors: Margenstern, Maurice | Verlan, Sergey | Rogozhin, Yurii

Article Type: Research Article

Abstract: Time-varying distributed H systems are a well known model of molecular computing. In this article we present an overview of this model, its history, related results, and open problems.

Keywords: Biomolecular computing, splicing systems, formal grammars

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 291-306, 2005

Authors: Mitrana, Victor

Article Type: Research Article

Abstract: This work is a continuation of [9]. We extend the multi-dimensional external contextual grammars introduced in the aforementioned work with the possibility of adjoining contexts in a selective way. An investigation of some mathematical properties (computational power and recognition complexity) of these new variants of contextual grammars is done via a constant comparison with the corresponding properties of classic Marcus external contextual grammars with or without choice.

Keywords: External contextual grammars, multi-dimensional external contextual grammars, range concatenation grammars

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 307-316, 2005

Authors: Mutyam, Madhu | Krithivasan, Kamala | Reddy, A. Siddhartha

Article Type: Research Article

Abstract: 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. Show more

Keywords: Insertion grammar, contextual grammar, recursively enumerable languages, Penttonen normal form, Kuroda normal form

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 317-324, 2005

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: The concept of a contextual grammar is slightly generalized here; the generalized grammars called contextual hypergrammars admit to introduce the so called reducing operators. Using some results concerning these operators a construction is described assigning a contextual grammar G_n (V,L) to any language (V,L) and to any nonnegative integer n. This construction has the following property: The language (V,L) is generated by a contextual grammar if and only if there exists a nonnegative …integer n_0 such that G_n =G_{n_0} (V,L) for any n ≥ n_0 . Show more

Keywords: Contextual hypergrammar, contextual grammar, reducing operator

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 325-340, 2005

Authors: Okhotin, Alexander | Salomaa, Kai

Article Type: Research Article

Abstract: A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

Keywords: Contextual grammar, trajectory, regular language, context-free language

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 341-351, 2005

Authors: Păun, Gheorghe | Pérez-Jiménez, Mario J. | Pazos, Juan | Rodríguez-Patón, Alfonso

Article Type: Research Article

Abstract: The operations of symport and antiport, directly inspired frombiology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also …for a small number of membranes, four. Show more

Keywords: Membrane computing, Turing computability, register machine, symport/antiport

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 353-367, 2005