Radial level planarity testing and embedding in linear time.
Radix enumeration of rational languages
We prove that the function that maps a word of a rational language onto its successor for the radix order in this language is a finite union of co-sequential functions.
Ragionando sul fallimento finito e le computazioni infinite usando l’interpretazione astratta
Ramanujan grammar and Cayley trees. (Grammaire de Ramanujan et arbres de Cayley.)
Ramsey partitions and proximity data structures
This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion.We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (also known as the non-linear version of the isomorphic Dvoretzky theorem,...
Ramsey theory applications.
Random generation for finitely ambiguous context-free languages
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
Random Generation for Finitely Ambiguous Context-free Languages
We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O(n2 log n) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1-NAuxPDA with polynomially bounded ambiguity.
Random -sat: the limiting probability for satisfiability for moderately growing .
Random Phenomena and Some Systems Generating Words
Random subnetworks of random sorting networks.
Randomized distributed access to mutually exclusive resources.
Range Searching with Efficient Hierarchical Cuttings.
Rank of tensors of -out-of- functions: An application in probabilistic inference
Bayesian networks are a popular model for reasoning under uncertainty. We study the problem of efficient probabilistic inference with these models when some of the conditional probability tables represent deterministic or noisy -out-of- functions. These tables appear naturally in real-world applications when we observe a state of a variable that depends on its parents via an addition or noisy addition relation. We provide a lower bound of the rank and an upper bound for the symmetric border rank...
Ranking and unranking of a generalized Dyck language and the application to the generation of random trees.
Rational approximation of rotation minimizing frames using Pythagorean-hodograph cubics.
Rational approximations to algebraic Laurent series with coefficients in a finite field
We give a general upper bound for the irrationality exponent of algebraic Laurent series with coefficients in a finite field. Our proof is based on a method introduced in a different framework by Adamczewski and Cassaigne. It makes use of automata theory and, in our context, of a classical theorem due to Christol. We then introduce a new approach which allows us to strongly improve this general bound in many cases. As an illustration, we give a few examples of algebraic Laurent series for which...
Rational stochastic automata in formal language theory
Rational strong codes and structure of rational group languages.
Rational tree relations.