Wyniki wyszukiwania - BazTech

1

On Metalinear CD Grammar Systems

Sunckel B.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

383-397

EN

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.

2

On Cooperating Distributed Grammar Systems with Competence Based Start and Stop Conditions

Dassow J.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

293-304

EN

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.

3

Grammar Systems versus Membrane Computing: The Case of CD Grammar Systems

Csuhaj-Varjú E., Paun G., Vaszil G.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

271-292

EN

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.

4

Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited

Bordihn H., Holzer M.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

255-270

EN

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.

5

Active Symbols in Pure Systems

Bensch S., Bordihn H.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

239-254

EN

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.

6

On a Connection Between Cooperating Distributed Grammar Systems and Basic Process Algebra

Csuhaj-Varju E., Mateescu A.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

37-50

EN

In this paper we discuss some relationships between cooperating distributed (CD) grammar systems and the basic process algebra (BPA) calculus. We associate different types of process graphs from this calculus to CD grammar systems which describe the behavior of the components of the system under cooperation. We prove that these process graphs form a subalgebra of the graph model of BPA. It is also shown that for certain restricted variants of CD grammar systems and for certain types of these process graphs the bisimilarity of two process graphs is decidable.