O biológii, matematike a výpočtoch - rozhovor s A. Lindenmayerom
Object grammars and random generation.
On a connection between algebra, logic and linguistics
On ambiguity in DOS systems
On context-free rewriting with a simple restriction and its computational completeness
This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems...
On differentiation functions, structure functions, and related languages of context-free grammars
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...
On differentiation functions, structure functions, and related languages of context-free grammars
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 k-narrow) iff its differentiation function is bounded by a constant (by k). 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 ...
On DOS languages and DOS mappings.
On hierarchy of the positioned eco-grammar systems
Positioned eco-grammar systems (PEG systems, for short) were introduced in our previous papers. In this paper we engage in a new field of research, the hierarchy of PEG systems, namely in the hierarchy of the PEG systems according to the number of agents presented in the environment and according to the number of types of agents in the system.
On morphically generated formal power series
On one of the boundaries of the constituent conception of grammar
On separating sets of words. I.
On separating sets of words. II.
On separating sets of words. III.
On separating sets of words. IV.
On separating sets of words. V.
On the equivalence of linear conjunctive grammars and trellis automata
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...
On the equivalence of linear conjunctive grammars and trellis automata
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...
On the generative capacity of colonies
On the periodicity of morphisms on free monoids