Fundamenta Informaticae - Volume 76, issue 3

Article Type: Other

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. i-iii, 2007

Authors: Bel-Enguix, Gemma | Jiménez-López, M. Dolores

Article Type: Research Article

Abstract: An application of membrane systems to natural languages study is presented. Specifically, we show how language change can be explained by using a new variant of membrane systems: Dynamic Meaning Membrane Systems (DMMS). By using DMMS, we model the main concepts of semantics and explain the three basic types of changes in meaning: broadening, narrowing and shift. Finally, we relate the membrane systems' application to language evolution with the suggested application of the so-called cultural grammar …systems to the same topic. Collaboration between the two frameworks may provide a useful formalism that, due to its naturalness and simplicity, might offer interesting results in a discipline traditionally far away from any formalization. Show more

Keywords: Membrane systems, grammar systems, language evolution, semantic change

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 219-237, 2007

Authors: Bensch, Suna | Bordihn, Henning

Article Type: Research Article

Abstract: In this paper, we consider the number of (statically measured) active symbols for Lindenmayer systems without interaction and some variants thereof as well as for pure CD grammar systems, where no distinction between terminal and nonterminal symbols is made. This measure of descriptional complexity gives rise to infinite hierarchies in all cases considered here. Moreover, all the devices under consideration are compared with respect to their generative power when the number of active symbols is bounded. …Finally, some closure and many non-closure properties of the corresponding language families with a fixed number of active symbols are proved. Show more

Keywords: Active symbols, Lindenmayer systems, cooperating distributed grammar systems, pure CD grammar systems

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 239-254, 2007

Authors: Bordihn, Henning | Holzer, Markus

Article Type: Research Article

Abstract: Based on a derivation mode f for cooperating distributed (CD) grammar systems, we introduce a new form of cooperation protocol, the so called "cut-f-mode" of derivation. Intuitively, in the cut-f-mode of derivation the sentential form is partitioned (cut) into several subwords, where some of these subwords are distributed to the components, which derive them according to the underlying f-mode of derivation, and finally the new sentential form is obtained by concatenating all the …subwords–derived or not–in their original order. According to the original motivation from distributed artificial intelligence, the new functioning mode appears to be more realistic than the original model. We investigate the cut-mode versions of the basic derivation modes and some of their combined versions. It turns out that in most cases, the cut-f-mode is at most as powerful as the corresponding non-cut-mode, that is, the f-mode itself. In some cases the power is even reduced to that of context-free grammars. Show more

Keywords: Cooperating distributed grammar systems, derivation modes, regulated rewriting, programmed grammars, finite index restriction, Lindenmayer languages

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 255-270, 2007

Authors: Csuhaj-Varjü, Erzsébet | Păun, Gheorghe | Vaszil, György

Article Type: Research Article

Abstract: In this paper we discuss some relationships between grammar systems and P systems (membrane systems), two areas of computer science dealing with distributed computing models, but with different motivations and different types of basic ingredients. We extend one of the most important communication protocols of cooperating distributed (CD) grammar systems, the so-called t-derivation mode, to P systems with string-objects: if no rule can be applied to a string in a region of a P system, then …the string is moved to a neighbouring region, depending on the communication mode either in exactly one direction (in or out) or in both directions. We describe the computational power of the obtained classes of P systems in comparison with families of languages generated by grammars in the Chomsky hierarchy or with CD grammar systems and formulate several problems for future research. Show more

Keywords: Cooperating distributed grammar systems, P systems

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 271-292, 2007

Authors: , Jürgen | Dassow,

Article Type: Research Article

Abstract: We define cooperating distributed grammar systems with start and stop conditions which are based on the competence of a component on the current sentential form. We distinguish six different types of competence conditions which result in 18 types of grammar systems. We summarize the results on the generative power known from the literature (where they are sometimes not related to competence) and determine the power of some further grammar systems.

Keywords: Cooperating distributed grammar systems, grammars with controlled derivations, ET0L systems

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 293-304, 2007

Authors: Freund, Rudolf | Oswald, Marion

Article Type: Research Article

Abstract: We consider tissue P systems where rules are applied when moving through a channel from one cell to another one. In a very general manner (i.e., working on arbitrary objects as strings, arrays, graphs, etc.), these tissue P systems equipped with the sequential derivation mode allow for the representation of hybrid co-operating grammar systems using the classic basic derivation modes *, t and ⩽ κ,= κ,⩾ κ, for κ ⩾ ℓ, as well as the internally …hybrid modes (⩾ κ∧⩽ℓ), for κ, ℓ∈N, κ⩽ℓ, and (t∧⩽κ), (t∧ =κ), (t∧⩾κ), for κ ⩾ 1. Moreover, we also show how these tissue P systems working in the sequential mode allow for the simulation of random context grammars, too. Show more

Keywords: Grammar system, tissue P system, derivation mode

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 305-323, 2007

Authors: Grando, María Adela | Mitrana, Victor

Article Type: Research Article

Abstract: The aim of this note is to show how parallel communicating grammar systems and concurrent programs might be viewed as related models for distributed and cooperating computation. We argue that a grammar system can be translated into a concurrent program, where one can make use of the Owicki-Gries theory and other tools available in the theory of concurrent programming. The converse translation is also possible and this turns out to be useful when we are looking …for a grammar system able to generate a given language. In order to show this, we use the language: L_{cd} = {a^n b^m c^n d^m ∣ n,m ⩾ 1}, called crossed agreement language, one of the basic non-context free constructions in natural and artificial languages. We prove, using tools from concurrent programming theory, that L_{cd} can be generated by a nonreturning parallel communicating grammar system with three regular components. We also discuss the absence of strategies in the concurrent programming theory to prove that L_{cd} cannot be generated by any parallel communicating grammar system with two regular components only, no matter the working strategy, but we prove this statement in the grammar system framework. Show more

Keywords: Parallel communicating grammar system, multiprogramming, Owicki-Gries theory

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 325-336, 2007

Authors: Kelemen, Jozef

Article Type: Research Article

Abstract: Eco-grammar (EG) systems are proposed as a suitable formal framework for the study of some of the computationally relevant properties of the behavior of collections of embodied agents sharing a common environment and acting in it in simple ways. It is illustrated that the computational power of such systems goes – in certain situations – beyond the traditional limits of the Turingcomputability.

Keywords: Agent, eco-grammar system, embodiment, formal grammar, computation, computability

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 337-347, 2007

Authors: Kelemenová, Alica | Tupý, Michal

Article Type: Research Article

Abstract: Two special cases of eco-grammar systems are studied, namely the systems with identical agents, called monocultures and the systems with homogeneous environment characterized by a unary alphabet. The generative power of these eco-grammar systems, given by the languages of the environments, is discussed. Introduced special cases restrict the generative power of eco-grammar systems. Hierarchy or incomparability of language classes with respect to the degree of eco-grammar systems, given by the number of the …agents, is shown for various cases of eco-grammar systems. Show more

Keywords: Eco-grammar system, monoculture, degree of an eco-grammar system, L-system, generative power

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 349-365, 2007

Authors: Sebestyén, Peter | Sosík, Petr

Article Type: Research Article

Abstract: We present a multi-robot model suitable for study of interactions and emergence of rational behavior. We focus on a grammatical approach, and to demonstrate its advantages, we design a model of an adaptive multi-robot community in terms of eco-grammar systems. We show that this grammatical model, based on the blackbord architecture, can naturally involve reinforcement collective learning. We test two learning algorithms in a common environment with almost reactive co-operating robots. Experimental results show that using …the grammatical model, the robot community can be successfully trained to find a close-to-optimal solution to a given NP-complete task of a truss construction. Show more

Keywords: Robotics, formal grammar, eco-grammar system

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 367-381, 2007

Authors: Sunckel, Bettina

Article Type: Research Article

Abstract: Metalinear CD grammar systems are defined to be context-free CD grammar systems where each component consists of metalinear productions. The maximal number of nonterminals in a starting production is the width of a CD grammar system. It will be shown that the width of metalinear CD grammar systems induces an infinite hierarchy of language classes. In addition, it is established that metalinear CD grammar systems of a certain width generate language classes that do not contain …all context-free languages but contain some context-sensitive languages. The resulting language classes are closed under union, intersection with regular languages, homomorphism and inverse homomorphism. They are not closed under concatenation, Kleene closure, intersection and complement. Show more

Keywords: Cooperating distributed grammar systems, metalinear grammars

Citation: Fundamenta Informaticae, vol. 76, no. 3, pp. 383-397, 2007