Automata and formal languages Large deviations Limit distributions Pattern statistics Rational series Regular languagesWe present a large deviation property for pattern statistics representing the number of occurrences of a symbol in words of given length generated at random according to a rational stochastic model.This result is proved assuming that the transition matrix of the model is primitive.We show how the rate function of the large deviation property depends on the main eigenvalues and eigenvectors of the transition matrices associated with the different symbols of the alphabet.We also yield general conditions to guarantee that the range of validity of the large deviation estimate coincides with the whole interval (0, 1), which represents in our context the largest possible open interval where the property may hold.The case of smaller intervals of validity is finally examined by means of examples.

We study the local limit distribution of the number of occurrences of a symbol in words of length n generated at random in a regular language according to a rational stochastic model. We present an analysis of the main local limits when the finite state automaton defining the stochastic model consists of two primitive components. The limit distributions depend on several parameters and conditions, such as the main constants of mean value and variance of our statistics associated with the two components, and the existence of communications from the first to the second component. The convergence rate of these results is always of order O(n−1/2). For the same statistics we also prove an analogous O(n−1/2) convergence rate of the Gaussian local limit law whenever the stochastic model consists of one primitive component.

In this paper we study the complexity of some size constrained clustering problems with norm Lp . We obtain the following results: (i) A separation property for the constrained 2-clustering problem. This implies that the optimal solutions in the 1-di

In this paper we consider the classes REC1 and UREC1 of unary picture languages that are tiling recognizable and unambiguously tiling recognizable, respectively. By representing unary pictures by quasi-unary strings we characterize REC1 (resp. UREC1) as the class of quasi-unary languages recognized by nondeterministic (resp. unambiguous) linearly space-bounded one-tape Turing machines with constraint on the number of head reversals. We apply such a characterization in two directions. First we prove that the binary string languages encoding tiling recognizable unary square languages lies between NTIME(2n) and NTIME(4n); by separation results, this implies there exists a non-tiling recognizable unary square language whose binary representation is a language in NTIME(4n log n). In the other direction, by means of results on picture languages, we are able to compare the power of deterministic, unambiguous and nondeterministic one-tape Turing machines that are linearly space-bounded and have constraint on the number of head reversals.