Laboratoire d'informatique de l'École polytechnique

News

Exposé par Hendrik Schrezenmaier: «Polygon contact representations»

Speaker: Hendrik Schrezenmaier
Location: BigBlueButton
Date: Mer. 6 mai. 2020, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi 6 mai à 10h30. Nous aurons le plaisir d’écouter Hendrik Schrezenmaier (TU Berlin).

L’exposé se tiendra en ligne par BigBlueButton.

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé : In a contact representation of a planar graph, the vertices of the graph are represented by objects in the plane with disjoint interiors and the edges correspond to touchings of these objects. The combinatorics of contact representations of planar triangulations with homothetic triangles are known to be described by Schnyder woods and the combinatorics of contact representations with axis-aligned rectangles are known to be described by transversal structures. In this talk, we will introduce a generalization of these structures that is suitable to describe the combinatorics of contact representations with regular K-gons for arbitrary K ≥ 5.

Afterwards, we will see how these structures can be used for the computation of the contact representations and for proving their existence. The idea of these methods is to associate a system of linear equations with each K-contact structure and to search for a K-contact structure whose system of equations has a non-negative solution. Then this solution encodes the contact representation. The way this search is done is quite beautiful and produces nice pictures.

This is joint work with Stefan Felsner and Raphael Steiner.

Partout Seminar: Nguyễn Lê Thành Dũng (LIPN), "Implicit automata in typed lambda-calculi"

Location: BigBlueButton
Date: Mon, 4 May 2020, 14:00-15:00

We show that various classes of languages and functions from automata theory can be equivalently defined using λ-calculi with substructural types. For instance, we characterize regular string-to-string functions with affine types, and star-free languages with non-commutative types. These results have few direct precedents, but they are analogous to the field of implicit computational complexity, except with automata instead of complexity classes. Our starting point is the little-known fact that the predicates definable over Church-encoded strings in the simply typed λ-calculus are exactly the regular languages (Hillebrand & Kanellakis, LICS’96). More recently, similar ideas have played a prominent role in higher-order model checking.

This is joint work with Pierre Pradic (University of Oxford).

The seminar will take place online. More information is available at: https://team.inria.fr/partout/seminar/