On separating sets of words. III.
On separating sets of words. IV.
On separating sets of words. V.
On Separating Two Simple Polygons by a Single Translation.
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 sets bounded truth-table reducible to -selective sets
On Shank's algorithm for modular square roots.
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 arithmetically expressible properties of programs
On some Basic Properties of the Kolmogorov Complexity
On some classes of tree automata and tree languages.
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.