Représentations matricielles des séries d'arbre reconnaissables
Representations of a free group of rank two by time-varying Mealy automata
In the group theory various representations of free groups are used. A representation of a free group of rank two by the so-calledtime-varying Mealy automata over the changing alphabet is given. Two different constructions of such automata are presented.
Representing real numbers in Möbius number systems
Réseaux systoliques pour des problèmes de mots
Retracts of free monoids are nowhere dense with respect to finite group topologies and p-adic topologies.
Returning and non-returning parallel communicating finite automata are equivalent
A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.
Reversals-space-parallelism tradeoffs for language recognition
Root clustering of words
Six kinds of both of primitivity and periodicity of words, introduced by Ito and Lischke [M. Ito and G. Lischke, Math. Log. Quart. 53 (2007) 91–106; Corrigendum in Math. Log. Quart. 53 (2007) 642–643], give rise to defining six kinds of roots of a nonempty word. For 1 ≤ k ≤ 6, a k-root word is a word which has exactly k different roots, and a k-cluster is a set of k-root words u where the roots of u fulfil a given prefix relationship. We show that out of the 89 different clusters that can be considered...
Rotations sur les groupes, nombres algébriques, et substitutions
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.