Repetitive strings are not context-free
Representable P. Martin-Löf tests
Représentation des nombres réels et calcul des fonctions élémentaires.
Représentation par automate de fonctions continues de tore
Soient et un sous-système. est une représentation en base d’une fonction du tore si pour tout point du tore, ses développements en base sont liés par le couplage aux développements en base de . On prouve que si est représentable en base alors , où . Réciproquement, toutes les fonctions de ce type sont représentables en base par un transducteur. On montre finalement que les fonctions du tore qui peuvent être représentées par automate cellulaire sont exclusivement les multiplications...
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
Representing Upper Probability Measures over Rational Lukasiewicz Logic.
Réseaux modulaires à structure variable
Si dà una formalizzazione dei moduli e delle reti modulari a struttura variabile. Si dimostra che per ogni automa finito a struttura variabile esiste una rete modulare a struttura variabile che lo simula. Si stabilisce il legame tra un automa a struttura variabile e l'automa a struttura variabile associato a una rete modulare a struttura variabile che lo simula.
Réseaux systoliques pour des problèmes de mots
Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...
Résultats de complétude pour des classes de types du système
Rétractions et interprétation interne du polymorphisme : le problème de la rétraction universelle
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
Reversibility in generalized Pascal triangles and binary reversibility in one-dimensional cellular automata
Rewriting on cyclic structures : equivalence between the operational and the categorical description
Rewriting on cyclic structures: Equivalence between the operational and the categorical description
We present a categorical formulation of the rewriting of possibly cyclic term graphs, based on a variation of algebraic 2-theories. We show that this presentation is equivalent to the well-accepted operational definition proposed by Barendregt et al. – but for the case of circular redexes , for which we propose (and justify formally) a different treatment. The categorical framework allows us to model in a concise way also automatic garbage collection and rules for sharing/unsharing and...