Displaying 601 – 620 of 948

Showing per page

Polynomial languages with finite antidictionaries

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

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.

Preface

Markus Holzer, Bianca Truthe (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Probabilistic models for pattern statistics

Massimiliano Goldwurm, Roberto Radicioni (2006)

RAIRO - Theoretical Informatics and Applications

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...

Probability timed automata for investigating communication processes

Henryk Piech, Grzegorz Grodzki (2015)

International Journal of Applied Mathematics and Computer Science

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,...

Propriétés arithmétiques des substitutions et automates infinis

Christian Mauduit (2006)

Annales de l’institut Fourier

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 u 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 d ( d entier positif), alors la suite ( n α ) n u ...

Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables

Julien Cassaigne, Marion Le Gonidec (2010)

Journal de Théorie des Nombres de Bordeaux

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 k -reconnaissables. Le cas particulier de l’ensemble des nombres premiers est également abordé.

Pumping and pushdown machines

Kai Salomaa, D. Wood, Sheng Yu (1994)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Pure interpretations of EOL forms

H. A. Maurer, G. Rozenberg, A. Salomaa, D. Wood (1979)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano (2006)

RAIRO - Theoretical Informatics and Applications

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...

Currently displaying 601 – 620 of 948