Tenseurs et machines
The behaviour of parsing time under grammar morphisms
The completely distributive lattice of machine invariant sets of infinite words
We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.
The computation of characteristic vectors of logical-probabilistic expressions
The cyclicity problem for the images of Q-rational series
We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.
The cyclicity problem for the images of Q-rational series
We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.
The decidability of the equivalence problem for polynomially bounded DOL sequences
The entropy of Łukasiewicz-languages
The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.
The entropy of Łukasiewicz-languages
The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.
The factor automaton
This paper concerns searching substrings in a string using the factor automaton. The factor automaton is a deterministic finite automaton constructed to accept every substring of the given string. Nondeterministic factor automaton is used to achieve new operations on factor automata for searching in non-constant texts.
The family of languages satisfying Bar-Hillel's lemma
The finite automata approaches in stringology
We present an overview of four approaches of the finite automata use in stringology: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions. We also show how the finite automata can process strings build over more complex alphabet than just single symbols (degenerate symbols, strings, variables).
The first-order theory of ordering constraints over feature trees.
The growth functions of finitely generated semigroups.
The independence of certain operations on semiAFLs
The insertion encoding of permutations.
The intersection problem for alphabetic vector monoids
The Ising transducer
The local catenativity of DOL-sequences in free commutative monoids is decidable in the binary case
The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues