On permutations generated by infinite binary words.
On possible growths of arithmetical complexity
The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More...
On racial insufficiency: White messengers cannot simulate coloured ones
On ranking 1-way finitely ambiguous NL languages and -complete census functions
On rational solution of the state equation of a finite automaton.
On real time and linear time cellular automata
On related transducers
On schemata and systems for parallel algorithms
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