Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

Uniformly bounded duplication codes

Peter LeupoldVictor Mitrana — 2007

RAIRO - Theoretical Informatics and Applications

Duplication is the replacement of a factor within a word by . This operation can be used iteratively to generate languages starting from words or sets of words. By undoing duplications, one can eventually reach a square-free word, the original word's duplication root. The duplication root is unique, if the length of duplications is fixed. Based on these unique roots we define the concept of duplication code. Elementary properties are stated, then the conditions under which infinite duplication...

Returning and non-returning parallel communicating finite automata are equivalent

Ashish ChoudharyKamala KrithivasanVictor Mitrana — 2007

RAIRO - Theoretical Informatics and Applications

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

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

Jürgen DassowVictor MitranaGheorghe PăunRalf 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 -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...

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

Jürgen DassowVictor MitranaGheorghe PăunRalf 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...

Page 1

Download Results (CSV)