Seminars

Title: Finding paths in large graphs

Abstract:
When dealing with large graphs, classical algorithms for finding paths such as Dijkstra's Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid this while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph.
I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications from DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average.
This is joint work with Charles Paperman.

Title: Containment for Probabilistic automata.

Abstract: This is an ICALP 2018 paper. We analyze when the model of probabilistic
automata has decidable properties, when restricting the ambiguity. The
notion of ambiguity is usually used in weighted automata or transducers,
but we follow a recent paper by Fijalkow, Riveros and Worrell, which
introduced this approach. We do not solve everything but our decidability
results rely unexpectedly on Schanuel's conjecture and we provide some
geometric intuition behind the hardness of the problem.

Abstract: The time complexity of 1-limited automata is investigated from a
descriptional complexity view point. Though the model recognizes
regular languages only, it may use quadratic time in the input length.
We show that, with a polynomial increase in size and preserving
determinism, each 1-limited automaton can be transformed into a
linear-time equivalent one. We also obtain polynomial transformations
into related models, including weight-reducing Hennie machines (i.e.,
one-tape Turing machines syntactically forced to operate in
linear-time), and we show exponential gaps for converse
transformations in the deterministic case.