Monoides pointes.
Monoïdes syntactiques et familles de langages rationnels
Motifs et bases de langages
Mots infinis
Mots infinis engendrés par une grammaire algébrique
Mots infinis et langages commutatifs
Mots infinis et produits de matrices a coefficients polynomiaux
Mots sans répétitions et langages rationnels bornés
Multi-dimensional sets recognizable in all abstract numeration systems
We prove that the subsets of that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
Multi-dimensional sets recognizable in all abstract numeration systems
We prove that the subsets of that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
Multigenerative grammar systems and matrix grammars
Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars....
Multi-island finite automata and their even computation
This paper discusses -island finite automata whose transition graphs can be expressed as -member sequences of islands , where there is a bridge leaving and entering for each . It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that -island finite automata...
Nested Sibling Tree Automata
In the XML standard, data are represented as unranked labeled ordered trees. Regular unranked tree automata provide a useful formalism for the validation of schemas enforcing regular structural constraints on XML documents. However some concrete application contexts need the expression of more general constraints than the regular ones. In this paper we propose a new framework in which context-free style structural constraints can be expressed and validated. This framework is characterized by: (i)...
Non literal tranducers and some problems of normality
A new proof of Maxfield’s theorem is given, using automata and results from Symbolic Dynamics. These techniques permit to prove that points that are near normality to base (resp. ) are also near normality to base (resp. ), and to study genericity preservation for non Lebesgue measures when going from one base to the other. Finally, similar results are proved to bases the golden mean and its square.
Non recursive functions have transcendental generating series
Nondeterminism versus determinism of finite automata over directed acyclic graphs.
Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
Non-générateurs algébriques et substitution
Normal forms for phrase-structure grammars
Normal forms for unary probabilistic automata
We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...