Special
Issue on Grammar Systems
Guest
Editor: J. Kelemen
Foreword
J.
Kelemen, Gh. Paun
Splicing
Grammar Systems
J.
Dassow, V. Mitrana
Abstract.
The aim of this paper is to bring together two new and powerful tools: on the
one hand, the splicing operation as a basic operation on DNA sequences and, on
the other
hand, the parallelism and communication features in grammar systems. As
expected, the result of the above combination is a very powerful mechanism,
leading to a new characterization of recursively enumerable languages.
Accepting
Multi-Agent Systems
H.
Fernau, M. Holzer, H. Bornihn
Abstract.
We consider cooperating distributed (CD) grammar systems and variants thereof as
language acceptors. If the CD grammar systems work in the modes £,
³,
=, or *, then their generating capacity equals their accepting capacity.
Contrary to this, we obtain a new characterization of the context-sensitive
languages by accepting CD grammar systems (with or without l-productions)
working in t-mode. Moreover, accepting
hybrid CD (HCD) grammar systems with l-productions
characterize the recursively enumerable languages.
Colonies
with Position
I.
Baník
Abstract.
In this paper, a new type of grammar colony is introduced. Its individual
components have some features of recognizing machines, nevertheless it is a
generative system. The name 'colonies with position' is proposed for it.
The class
Lcol
P(1)
of languages generated by colonies
of such components (Lcol
P)
are investigated. Colonies
with position were proven to generate the class of context-sensitive languages,
while the individual components generate finite languages only.
On
the Generative Capacity of PCGDCs
with Regular Components
V.
Mihalache
Abstract.
The paper considers
the simplest class of parallel communicating grammar systems (PCGSs),
namely with regular components, which yet seems to be not enough investigated.
It is proved that in the centralized returning case (deriving in the usual mode)
and in the non-centralized non-returning case with terminal derivation the
systems are not "too powerful", more exactly they can be simulated by
finite index matrix grammars.
Collapsing
Hierarchies in PCGSs with Communication by Commands
L.
Ilie
Abstract.
WE investigate here, mainly from the point of view of the hierarchies generated
by different classes of systems, two variants of the parallel communicating
grammar systems (PCGS) with communication by command:
the multiple and, respectively, the single communication case. We show
that the hierarchies for regular and linear components collapse in the single
communication case and the hierarchy for context-sensitive components collapses
in both multiple and single communication cases. By a result in [3], it will
follow from our result on systems with context-sensitive components that also
the hierarchy for context-free components collapses in both cases. Some open
problems are also formulated.
PCGSs
Without a Master
Gy.
Vaszil
Abstract.
Two new derivation
modes are introduced for parallel communicating grammar systems (PCGSs).
One of them is called competitive, the other is called popular, they both
eliminate the hierarchy among the component grammars. The generative power of
parallel communicating grammar systems working in these new modes is
investigated, with different types of grammars and extended Lindenmayer systems
as components.
The
Computational Complexity of Linear PCGSs
L.
Cai
Abstract.
The computational complexity is investigated for Parallel Communicating Grammar
Systems (PCGSs) whose components are linear grammars. It is shown that language
generated by linear PCGSs can be recognized by O(log
n) space/bounded Turing machines.
Based on the complexity characterization, the generative power of linear PCGSs
is analyzed with respect to context-free and context-sensitive grammars.
Test
Tube Distributed Systems Based on Splicing
E.
Csuhaj-Varjú, L. Kari, Gh. Paun
Abstract.
We define a symbol processing mechanism with the components (test tubes) working
as splicing schemes in the sense of T. Head and communicating by redistributing
the contents of tubes (in a similar way to the separate
operation of Lipton-Adleman). (These systems are similar to the distributed
generative mechanisms called Parallel Communicating Grammar Systems.) Systems
with finite initial contents of tubes and finite sets of splicing rules
associated to each component are computationally complete, they characterize the
family of recursively enumerable languages. The existence of universal test tube
distributed systems is obtained on this basis, hence the theoretical proof of
the possibility to design universal programmable computers with the structure of
such a system.
On
Cooperatively Distributed Ciphering and Hashing
C.
Ding, A. Salomaa
Abstract.
In this paper we first bridge some problems of formal language theory to those
of cryptography. In doing so, new problems in both fields are proposed.
Motivated by the CD grammar systems [1], we then describe a general
cooperatively distributed ciphering system and hashing system. These CD
ciphering and hashing systems could be much more powerful than conventional ones
if they are properly designed.
On
Eco-Grammar Systems and Artificial Neural Networks
P.
Sosík
Abstract.
Eco-grammar systems and artificial neural networks have many common features:
massive parallelism, independently working elements (agents/neurons),
cooperation of the elements and, not least, universal computational power (at
least as that of Turing machine).
We
prove the possibility to simulate each step of a system of one of the types by a
fixed number of steps of a system of the other type without loss of parallelism.
Moreover, the number of processing elements (neurons, agents) of the model is a
function of class O (n), where n
is a number of processing elements of the original system.