On semidirect products of two finite semilattices.
On semigroups of matrices over the tropical semiring
On sequences defined by D0L power series
On Sequences Defined by D0L Power Series
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 for all n ≥ 0. As a consequence we solve the equivalence problem of D0L power series over computable fields.
On shuffle ideals
A shuffle ideal is a language which is a finite union of languages of the form where is a finite alphabet and the ’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
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 simple matrix languages versus scattered context languages
On simple representations of language families
On Simple Stochastic Models
On some closure properties of generable languages
On some context free languages that are not deterministic ETOL languages
On some elementary properties of uniform automata
On some factorization problems.
On some machine sequencing problems (II)
On star height hierarchies of context-free languages
On State Reduction In Deterministic Finite Transducers And Some Properties Of Deterministic Regular Translations
On strong homomorphisms of finitely semigenerated languages
On subword complexities of homomorphic images of languages
On synchronized sequences and their separators
We introduce the notion of a -synchronized sequence, where is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be -synchronized if its graph is represented, in base , by a right synchronized rational relation. This is an intermediate notion between -automatic and -regular sequences. Indeed, we show that the class of -automatic sequences is equal to the class of bounded -synchronized sequences and that the class of -synchronized sequences is strictly...
On synchronized sequences and their separators
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...