Source author record

Julien David

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Formal Languages and Automata Theory math.MG

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Elementary moves on lattice polytopes

We introduce a graph structure on Euclidean polytopes. The vertices of this graph are the $d$ -dimensional polytopes contained in $\mathbb{R}^d$ and its edges connect any two polytopes that can be obtained from one another by either inserting or deleting a vertex, while keeping their vertex sets otherwise unaffected. We prove several results on the connectivity of this graph, and on a number of its subgraphs. We are especially interested in several families of subgraphs induced by lattice polytopes, such as the subgraphs induced by the lattice polytopes with $n$ or $n+1$ vertices, that turn out to exhibit intriguing properties.

preprint2016arXiv

Parallel Galton Watson Process

In this paper, we study a parallel version of Galton-Watson processes for the random generation of tree-shaped structures. Random trees are useful in many situations (testing, binary search, simulation of physics phenomena,...) as attests more than 49000 citations on Google scholar. Using standard analytic combinatorics, we first give a theoretical, average-case study of the random process in order to evaluate how parallelism can be extracted from this process, and we deduce a parallel generation algorithm. Then we present how it can be implemented in a task-based parallel paradigm for shared memory (here, Intel Cilk). This implementation faces several challenges, among which efficient, thread-safe random bit generation, memory management and algorithmic modifications for small-grain parallelism. Finally, we evaluate the performance of our implementation and the impact of different choices and parameters. We obtain a significant efficiency improvement for the generation of big trees. We also conduct empirical and theoretical studies of the average behaviour of our algorithm.

preprint2011arXiv

Asymptotic enumeration of Minimal Automata

We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over the possible transition structures, and a binomial distribution over terminal states, with arbitrary parameter b. It turns out that a fraction ~ 1-C(k,b) n^{-k+2} of automata is minimal, with C(k,b) a function, explicitly determined, involving the solution of a transcendental equation.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.