Über die darstellbarkeit des syntaktischen monoïdes kontextfreier sprachen
Un algorithme de calcul formel des séries énumératrices de langage linéaire
Un cadre algébrique pour l'étude des monoïdes syntactiques
Un générateur inhéremment ambigu du cône des langages algébriques
Un langage algébrique particulier
Un langage quasi-rationnel lié aux graphes planaires
Un nouveau type de preuve mathématique : le théorème des quatre couleurs. I - Exposé préliminaire
Un nouveau type de preuve mathématiques : II - Le théorème des quatre couleurs
Un problème combinatoire de la théorie des codes
Un réseau linéaire pour la reconnaissance des mots sans carré
Un résultat sur le quotient de Hadamard des séries rationnelles
Unambiguous recognizable two-dimensional languages
We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of...
Unavoidable languages, cuts and innocent sets of words
Undecidability of the equivalence of finite substitutions on regular language
Undecidability of the equivalence of finite substitutions on regular language
A simplified proof is given for the following result due to Lisovik: it is undecidable for two given ε–free finite substitutions, whether they are equivalent on the regular language b{0,1}*c.
Undecidability of topological and arithmetical properties of infinitary rational relations
We prove that for every countable ordinal one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether...
Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide...
Une application des notions de centre et index rationnel à certains langages algébriques
Une caractérisation des générateurs standard
Une caractérisation des langages algébriques bornés