The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying 61 – 80 of 142

Showing per page

On Sequences Defined by D0L Power Series

Juha Honkala (2010)

RAIRO - Theoretical Informatics and Applications

We study D0L power series over commutative semirings. We show that a sequence (cn)n≥0 of nonzero elements of a field A is the coefficient sequence of a D0L power series if and only if there exist a positive integer k and integers βi for 1 ≤ i ≤ k such that c n + k = c n + k - 1 β 1 c n + k - 2 β 2 ... c n β k for all n ≥ 0. As a consequence we solve the equivalence problem of D0L power series over computable fields.

On shuffle ideals

Pierre-Cyrille Héam (2002)

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

A shuffle ideal is a language which is a finite union of languages of the form A * a 1 A * A * a k A * where A is a finite alphabet and the a i ’s are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally...

On Shuffle Ideals

Pierre-Cyrille Héam (2010)

RAIRO - Theoretical Informatics and Applications


A shuffle ideal is a language which is a finite union of languages of the form A*a1A*...A*ak where A is a finite alphabet and the ai's are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for...

On synchronized sequences and their separators

Arturo Carpi, Cristiano Maggi (2001)

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

We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly...

On synchronized sequences and their separators

Arturo Carpi, Cristiano Maggi (2010)

RAIRO - Theoretical Informatics and Applications

We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is...

Currently displaying 61 – 80 of 142