Safety- and liveness-properties in propositional temporal logic: characterizations and decidability
Saturating right congruences
Self-reproducing pushdown transducers
After a translation of an input string, , to an output string, , a self- reproducing pushdown transducer can make a self-reproducing step during which it moves to its input tape and translates it again. In this self- reproducing way, it can repeat the translation -times for any . This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than...
Semantic analysis of an ALGOL text
Sémantique algébrique de l'appel par valeur
Sémantique des structures de contrôle
Sémantique formelle des opérateurs d'un langage de listes
Semi-commutations and partial commutations
Semi-commutations and Partial commutations
The aim of this paper is to show that a semi-commutation function can be expressed as the compound of a sequential transformation, a partial commutation function, and the reverse transformation. Moreover, we give a necessary and sufficient condition for the image of a regular language to be computed by the compound of two sequential functions and a partial commutation function.
Semigroups defined by automaton extension mapping
We study semigroups generated by the restrictions of automaton extension (see, e.g., [3]) and give a characterization of automaton extensions that generate finite semigroups.
Semisimplicity of the algebra associated to a biprefix code.
Separating words with machines and groups
Sequential mappings of -languages
Sequential monotonicity for restarting automata
As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only...
Séries algébriques solutions d'équations linéaires avec opérateurs
Séries formelles
La classification chomskienne des langages formels conduit à l'étude d'objets mathématiques nouveaux: les séries rationnelles et algébriques en variables non commutatives.
Séries formelles rationnelles et reconnaissables
Séries rationnelles
Séries rationnelles à plusieurs variables non commutatives, Hadamard-inversibles
Series which are both max-plus and min-plus rational are unambiguous
Consider partial maps with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure...