Constructing Arrangements Optimally in Parallel.
Construction, évaluation et amélioration systématiques de structures de données
Construction of e-Nets.
Context-free languages with rational index in for algebraic numbers
Convergence of a branching type recursion
Convolutive decomposition and fast summation methods for discrete-velocity approximations of the Boltzmann equation
Discrete-velocity approximations represent a popular way for computing the Boltzmann collision operator. The direct numerical evaluation of such methods involve a prohibitive cost, typically O(N2d + 1) where d is the dimension of the velocity space. In this paper, following the ideas introduced in [C. Mouhot and L. Pareschi, C. R. Acad. Sci. Paris Sér. I Math. 339 (2004) 71–76, C. Mouhot and L. Pareschi, Math. Comput. 75 (2006) 1833–1852], we derive fast summation techniques for the evaluation of...
Counterexamples in optimal quadrature.
Counting Triangle Crossings and Halving Planes.
Crossing-bounded computations and their relation to the LBA-problem
Cutting Hyperplane Arrangements.
D0L sequence equivalence is in for fixed alphabets
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of -rational sequences.
D0L sequence equivalence is in P for fixed alphabets
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of -rational sequences.
Deciding inclusion of set constants over infinite non-strict data structures
Various static analyses of functional programming languages that permit infinite data structures make use of set constants like Top, Inf, and Bot, denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. This...
Des algorithmes linéaires pour les problèmes de partition, de recouvrement et de couplage dans les hypergraphes d'intervalles
Description of the Connected Components of a Semialgebraic Set in Single Exponential Time.
Détermination de la représentation standard d'une série reconnaissable
Die Berechnungskomplexität von elementarsymmetrischen Funkit
Die mit Nestedstackautomaten berechenbaren Funktionen sind elementar.
Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems
We obtain new results regarding the precise average-case analysis of the main quantities that intervene in algorithms of a broad Euclidean type. We develop a general framework for the analysis of such algorithms, where the average-case complexity of an algorithm is related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory and provide...
Drawing graphs on two and three lines.