Una teoria algebrica per i «guarded commands» di Dijkstra
Unambiguous erasing morphisms in free monoids
This paper discusses the fundamental combinatorial question of whether or not, for a given string α, there exists a morphism σ such that σ is unambiguous with respect to α, i.e. there exists no other morphism τ satisfying τ(α) = σ(α). While Freydenberger et al. [Int. J. Found. Comput. Sci. 17 (2006) 601–628] characterise those strings for which there exists an unambiguous nonerasing morphism σ, little is known about the unambiguity of erasing morphisms, i.e. morphisms that map symbols...
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...
Undecidable event detection problems for ODEs of dimension one and two
Une application des notions de centre et index rationnel à certains langages algébriques
Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes
Une caractérisation des générateurs standard
Une caractérisation des langages algébriques bornés
Une charpente de semi-unification
Une condition impliquant toutes les identités rationnelles
Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
Une critique de la notion de test de processus fondée sur la non séparabilité de certaines classes de langages
Une double hiérarchie infinie de langages vérifiables
Une extension des langages déterministes
Une extension d'un théorème de P. Jullien sur les âges de mots