We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular...
In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors is conducted in different ways, have the same computational...
In this paper, we introduce generating networks of splicing processors (GNSP for short),
a formal languages generating model related to networks of evolutionary processors and to
accepting networks of splicing processors. We show that all recursively enumerable
languages can be generated by GNSPs with only nine processors. We also show, by direct
simulation, that two other variants of this computing model, where the communication
between processors...
We define H- and EH-expressions as extensions of regular
expressions by adding homomorphic and iterated homomorphic
replacement as new operations, resp. The definition is analogous to
the extension given by Gruska in order to characterize context-free
languages. We compare the families of languages obtained by these
extensions with the families of regular, linear context-free,
context-free, and EDT0L
languages. Moreover, relations to
language families based on patterns, multi-patterns,...
We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or -narrow) iff its differentiation function is bounded by a constant (by ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of the equivalence...
We introduce the notion of a differentiation function of a
context-free grammar which gives the number of terminal words that can be
derived in a certain number of steps. A grammar is called narrow (or
-narrow) iff its differentiation function is bounded by a constant
(by ). We present the basic properties of differentiation functions,
especially we relate them to structure function of context-free languages
and narrow grammars to slender languages. We discuss the decidability of
the...
Download Results (CSV)