All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 5 Next

Displaying 81 – 100 of 138

Showing per page

On differentiation functions, structure functions, and related languages of context-free grammars

Jürgen Dassow, Victor Mitrana, Gheorghe Păun, Ralf Stiebe (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 the equivalence...

On differentiation functions, structure functions, and related languages of context-free grammars

Jürgen Dassow, Victor Mitrana, Gheorghe Păun, Ralf Stiebe (2010)

RAIRO - Theoretical Informatics and Applications

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 hierarchy of the positioned eco-grammar systems

Miroslav Langer (2014)

Kybernetika

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 the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Alexander Okhotin (2010)

RAIRO - Theoretical Informatics and Applications

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...

One-Rule Length-Preserving Rewrite Systems and Rational Transductions

Michel Latteux, Yves Roos (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u = xyz and v = zyx. We...

Currently displaying 81 – 100 of 138