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