We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences...
Exploitation characteristics behaves as a decreasing valors factor (DVF) which can be connected with degradation processes. It is a structure that consists of independent attributes which represent situations generally connected with a given exploitation factor. The multi-attribute structure contains attributes directly and indirectly referring to the main factor. Attribute states, by definition, can only maintain or decrease their values. Such situations are met in security, reliability, exploitation,...
L’objet de ce travail est d’étudier les propriétés arithmétiques et statistiques des mots infinis et des suites de nombres entiers engendrés par des substitutions sur un alphabet infini ou par des automates déterministes ayant un nombre infini dénombrable d’états. En particulier, nous montrons que si est une suite de nombres entiers engendrée par un automate dont le graphe étiqueté associé représente une marche aléatoire de moyenne nulle sur un réseau de ( entier positif), alors la suite ...
Nous étudions dans cet article deux familles d’ensembles d’entiers reconnaissables par des automates finis ou dénombrables. Les résultats concernant ces deux notions de reconnaissabilité qui sont présentés ici étendent de manière naturelle les résultats structurels usuels de la famille des ensembles -reconnaissables. Le cas particulier de l’ensemble des nombres premiers est également abordé.
Bertoni et al. introduced in Lect. Notes Comput. Sci.2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted...