Langages d'interprétation des schémas récursifs
Langages persistants
Langages très simples générateurs
Language classes defined by time-bounded relativised cellular automata
Languages obtained from infinite words
Languajes and monoids with disjuntive identity.
Le problème des roulements de quarts pour les entreprises à feu continu
Learning deterministic regular grammars from stochastic samples in polynomial time
Learning deterministic regular grammars from stochastic samples in polynomial time
In this paper, the identification of stochastic regular languages is addressed. For this purpose, we propose a class of algorithms which allow for the identification of the structure of the minimal stochastic automaton generating the language. It is shown that the time needed grows only linearly with the size of the sample set and a measure of the complexity of the task is provided. Experimentally, our implementation proves very fast for application purposes.
Learning extremal regulator implementation by a stochastic automaton and stochastic approximation theory
There exist many different approaches to the investigation of the characteristics of learning system. These approaches use different branches of mathematics and, thus, obtain different results, some of them are too complicated and others do not match the results of practical experiments. This paper presents the modelling of learning systems by means of stochastic automate, mainly one particular model of a learning extremal regulator. The proof of convergence is based on Dvoretzky's Theorem on stochastic...
Learning tree languages from text
We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [Theoret. Comput. Sci.290 (2003) 1679–1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update time...
Left-to-right regular languages and two-way restarting automata
It is shown that the class of left-to-right regular languages coincides with the class of languages that are accepted by monotone deterministic RL-automata, in this way establishing a close correspondence between a classical parsing algorithm and a certain restricted type of analysis by reduction.
Les automates circulaires biaisés vérifient la conjecture de Černý
Les automates formels appliqués à l'étude et à la classification des modèles économétriques
Levels in L-systems
Locally testable semigroups.
Logarithmic frequency in morphic sequences
We study the logarithmic frequency of letters and words in morphic sequences and show that this frequency must always exist, answering a question of Allouche and Shallit.
Logic and -recognizable sets of integers.
Loops in automata and HDTOL relations
Lower bounds for Las Vegas automata by information theory
We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction...