BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Automates seminar of IRIF
NAME:Automates
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Automates seminar of IRIF
X-WR-CALNAME:Automates
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Entropy games and matrix multiplication games - Eugene Asarin\, IR
IF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160318T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160318T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:17
DESCRIPTION:Two intimately related new classes of games are introduced and
studied: entropy games (EGs) and matrix multiplication games (MMGs). An E
G is played on a finite arena by two-and-a-half players: Despot\, Tribune
and the non-deterministic People. Despot wants to make the set of possible
People’s behaviors as small as possible\, while Tribune wants to make i
t as large as possible. An MMG is played by two players that alternately w
rite matrices from some predefined finite sets. One wants to maximize the
growth rate of the product\, and the other to minimize it. We show that in
general MMGs are undecidable in quite a strong sense. On the positive sid
e\, EGs correspond to a subclass of MMGs\, and we prove that such MMGs and
EGs are determined\, and that the optimal strategies are simple. The comp
lexity of solving such games is in NP ∩ coNP.\n\nJoint work with Julien
Cervelle\, Aldric Degorre\, Cătălin Dima\, Florian Horn\, and Victor Koz
yakin.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Determination and Prediction of Infinite Words by Automata - Tim S
mith\, LIGM Paris Est
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160401T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160401T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:20
DESCRIPTION:An infinite language L determines an infinite word α if every
string in L is a prefix of α. If L is regular\, it is known that α mus
t be ultimately periodic\; conversely\, every ultimately periodic word is
determined by some regular language. We investigate other classes of lang
uages to see what infinite words they determine\, focusing on languages re
cognized by various kinds of automata.\n\nNext\, we consider prediction of
infinite words by automata. In the classic problem of sequence predictio
n\, a predictor receives a sequence of values from an emitter and tries to
guess the next value before it appears. The predictor masters the emitter
if there is a point after which all of the predictor's guesses are correc
t. We study the case in which the predictor is an automaton and the emitt
ed values are drawn from a finite set\; i.e.\, the emitted sequence is an
infinite word.\n\nThe automata we consider are finite automata\, pushdown
automata\, stack automata (a generalization of pushdown automata)\, and mu
ltihead finite automata\, and we relate them to purely periodic words\, ul
timately periodic words\, and multilinear words.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sturmian colorings on regular trees - Dong Han Kim\, Dongguk Unive
rsity\, Corée du Sud
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160513T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160513T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:47
DESCRIPTION:We introduce Sturmian colorings of regular trees\, which are c
olorings\nof minimal\nunbounded factor complexity.\nThen\, we classify Stu
rmian colorings into two families\, namely cyclic\nand acyclic ones.\nWe c
haracterize acyclic Sturmian colorings in a way analogous to\ncontinued fa
ction algorithm of Sturmian words.\nAs for cyclic Sturmian colorings\, we
show that the coloring is a\ncountable union of a periodic coloring\, poss
ibly union with a regular\nsubtree colored with one color.\n\nThis is join
t work with Seonhee Lim.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Un jeu apériodique de 11 tuiles - Emmanuel Jeandel\, LORIA
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160415T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160415T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:48
DESCRIPTION:Une tuile de Wang est un carré dont les bords sont colorés.\
nÉtant donné un ensemble fini de tuiles de Wang\, on cherche à savoir\n
s'il est possible de paver le plan discret tout entier avec ces tuiles\, \
nen mettant une\ntuile par case de sorte que deux tuiles adjacentes aient
la même\ncouleur sur le bord qu'elles partagent. On s'intéresse plus\npa
rticulièrement aux jeux de tuiles apériodiques\, ceux pour lesquels\nun
pavage existe\, mais où il est impossible de paver le plan\npériodiqueme
nt. Ces jeux de tuiles sont une des briques de base de la \nmajorité des\
nrésultats en dynamique symbolique multidimensionnelle.\n\nLe premier jeu
de tuiles apériodique trouvé par Berger avait 20426 \ntuiles\, et le\nn
ombre de tuiles nécessaire a baissé progressivement jusqu'à ce que\nCul
ik obtienne en 1996 un jeu de 13 tuiles en utilisant une méthode\ndue à
Kari.\n\nAvec Michael Rao\, nous avons trouvé avec l'aide de plusieurs\no
rdinateurs un jeu apériodique de 11 tuiles. Ce nombre est optimal : il\nn
'existe pas de jeu apériodique de moins de 11 tuiles. Une des\nprincipal
es difficultés de cette recherche guidée par ordinateur est\nque nous ch
erchons une aiguille dans une botte de foin indécidable : il\nn'existe pa
s d'algorithme qui décide si un jeu de tuiles est\napériodique.\n\nAprè
s une brève introduction au problème\, je présenterai l'ensemble de\n11
tuiles\, ainsi que les techniques de théorie des automates et de\nsystè
mes de transitions qui ont permis de prouver (a) qu'il est\napériodique\,
et (b) que c'est le plus petit.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matrix Semigroups and Related Automata Problems - Igor Potapov\, U
niversity of Liverpool
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160520T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160520T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:49
DESCRIPTION:Matrices and matrix products play a crucial role in a represen
tation and analysis of various computational processes. \nUnfortunately\,
many simply formulated and elementary problems for matrices are inherently
difficult to solve even \nin dimension two\, and most of these problems b
ecome undecidable in general starting from dimension three or four.\nLet u
s given a finite set of square matrices (known as a generator) which is fo
rming a multiplicative semigroup S. \nThe classical computational problems
for matrix semigroups are:\n * Membership (Decide whether a given matrix
M belong to a semigroup S) and special cases such as: Identity (i.e if M
is the identity matrix) and Mortality (i.e if M is the zero matrix) proble
ms\n * Vector reachability (Decide for a given vectors u and v whether ex
ist a matrix M in S such that Mu=v)\n * Scalar reachability (Decide for a
given vectors u\, v and a scalar L whether exist a matrix M in S such tha
t uMv=L)\n * Freeness (Decide whether every matrix product in S is uniqu
e\, i.e. whether it is a code)\nThe undecidability proofs in matrix semigr
oups are mainly based on various techniques and methods for embedding univ
ersal \ncomputations into matrix products. The case of dimension two is th
e most intriguing since there is some evidence that if these \nproblems ar
e undecidable\, then this cannot be proved using any previously known cons
tructions. Due to a severe lack of methods \nand techniques the status of
decision problems for 2x2 matrices (like membership\, vector reachability\
, freeness) is remaining to be \na long standing open problem. More recent
ly\, a new approach of translating numerical problems of 2x2 integer matri
ces into variety \nof combinatorial and computational problems on words an
d automata over group alphabet and studying their transformations as speci
fic rewriting \nsystems have led to a few results on decidability and comp
lexity for some subclasses.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Generalised Twinning Property for Minimisation of Cost Register
Automata - Laure Daviaud\, LIP – ENS Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160527T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160527T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:56
DESCRIPTION:Weighted automata (WA) extend finite-state automata defining f
unctions from the set of words to a semiring S. Recently\, cost register a
utomata (CRA) have been introduced as an alternative model to describe any
function realised by a WA by means of a deterministic machine.\n\nRegardi
ng unambiguous WA over a group G\, they can equivalently be described by a
CRA whose registers take their values in G\, and are updated by operation
s of the form X:=Y.c\, with c in G and X\,Y registers.\n\nIn this talk\, I
will give a characterisation of unambiguous weighted automata which are e
quivalent to cost register automata using at most k registers\, for a give
n k. To this end\, I will generalise two notions originally introduced by
Choffrut for finite-state transducers: a twinning property and a bounded v
ariation property\, here parametrised by an integer k and that characteris
e WA/functions computing by a CRA using at most k registers.\n\nThis is a
joint work with Pierre-Alain Reynier and Jean-Marc Talbot.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Two Variable Logic with a Between Predicate - Howard Straubing\, B
oston College
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160603T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160603T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:60
DESCRIPTION:We study an extension of FO^2[<]\, first-order logic interpre
ted in finite words in which only two variables are used. We adjoin to th
is language two-variable atomic formulas that say\, 'the letter a appears
between positions x and y'. This is\, in a sense\, the simplest property
that is not expressible using only two variables.\n\nWe present several lo
gics\, both first-order and temporal\, that have the same expressive power
\, and find matching lower and upper bounds for the complexity of satisfia
bility for each of these formulations. We also give an effective algebra
ic characterization of the properties expressible in this logic. This ena
bles us to prove\, among many other things\, that our new logic has strict
ly less expressive power than full first-order logic FO[<].\n\nThis is joi
nt work with Andreas Krebs\, Kamal Lodaya\, and Paritosh Pandya\, and will
be presented at LICS2016.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Perfect-information Stochastic Priority Games - Bruno Karelovic\,
IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160610T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160610T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:69
DESCRIPTION:We present in this work an alternative solution to perfect-inf
ormation stochastic parity games. Instead of using the framework of μ-cal
culus\, which hides completely the algorithmic aspect\, we solve it by ind
uction on the number of absorbing states.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Deterministic Automaton and FO[<\,mod] integer set - Arthur Milchi
or\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160617T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160617T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:70
DESCRIPTION:We consider deterministic automata which accept vectors of d\n
integers for a fixed positive integer d. A deterministic automaton is\nth
en a finite representation of the sets of vectors it accepts. Many\noperat
ions are particularly efficient with this representation\, such\nas inters
ection of sets\, testing whether two sets are equal or\ndeciding whethersu
ch an automaton accepts a Presburger-definable set\,\nthat is a FO[+\,<]-d
efinable set over integers. We consider a similar\nproblem for less expre
ssive logics such as FO[<\,0\,moda] or\n\\FO[+1\,0\,mod]\, where mod is th
e class of modular relations.\n\nWe state that it is decidable in time O(n
log(n)) whether a set of\nvectors accepted by a given finite deterministic
automaton can be\ndefined in the less expressive logic. The case of dimen
sion 1 was\nalready proven by Marsault and Sakarovitch. If the first algor
ithms\ngives a positive answer\, the second one computes in time\nO(n^{3}l
og(n)) an existential formula in this logic that defines the\nsame set. Th
is improves the 2EXP time algorithm that can be easily\nobtained by combin
ing the results of Leroux and Choffrut.\n\nIn this talk\, it is intended t
o:\n-Introduce automata reading vectors of integers\,\n-Present the logic
FO[<\,0\,mod] over integers\n-Introduce classical tools relating automata
to numbers.\n-Give an idea of how they can be applied to the above-mention
ned problem.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Soutenance de Thèse : Two-wayness: Automata and Transducers - Bru
no Guillon\, IRIF - Universitá degli Studi di Milano
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160530T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160530T150000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:82
DESCRIPTION:This PhD is about two natural extensions of Finite Automata: t
he 2-way FA (2FA) and the 2-way transducers (2T).\n\nThe 2FA are computabl
y equivalent to FA\, even in their nondeterministic (2NFA) variant. Howeve
r\, in the Descriptional Complexity area\, some questions remain. Raised b
y Sakoda and Sipser in 1978\, the question of the cost of the simulation o
f 2NFA by 2DFA is still open. In this manuscript I give an answer in a res
tricted case in which the nondeterministic choices of the 2NFA may occur a
t the border of the input only (2ONFA). I show that every 2ONFA can be sim
ulated by a 2DFA of subexponential (but superpolynomial) size. Under the a
ssumptions L=NL\, this cost is reduced to the polynomial level. Moreover\,
I prove that the complementation\, and the simulation by a halting 2ONFA
is polynomial.\n\nClassical transducers (1-way) are well-known and admit n
ice characterizations (rational relations\, logic). But their 2-way varian
t (2T) is still unknown\, especially the nondeterministic case. In this ar
ea\, my manuscript gives a new contribution: a algebraic characterization
of the relations accepted by 2NT when both the input and output alphabets
are unary. It can be reformulated as follows: each unary 2NT is equivalent
to a sweeping (and even rotating) 2T. I also show that the assumptions ma
de on the size of the alphabets are required.\n\nThe study of word relatio
ns\, as algebraic object\, and their transitive closure is another subject
considered in my phd. When the relation belongs to some low level class\,
we are able to set the complexity of its transitive closure. This quickly
becomes uncomputable when higher classes are considered.
LOCATION:Salle des thèse (halle aux farines)
END:VEVENT
BEGIN:VEVENT
SUMMARY:Solving Equations on Words with Morphisms and Antimorphisms - Sylv
ain Hallé\, Université du Québec à Chicoutimi
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160708T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160708T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:87
DESCRIPTION:Word equations are combinatorial equalities between strings of
symbols\, variables and functions\, which can be used to model problems i
n a wide range of domains. While some complexity results for the solving o
f specific classes of equations are known\, currently there does not exist
any equation solver publicly available. Recently\, we have proposed the i
mplementation of such a solver based on Boolean satisfiability that levera
ges existing SAT solvers for this purpose. In this paper\, we propose a ne
w representation of equations on words having fixed length\, by using an e
nriched graph data structure. We discuss the implementation as well as exp
erimental results obtained on a sample of equations.
LOCATION:Salle 1003
END:VEVENT
BEGIN:VEVENT
SUMMARY:Journée de rentrée - Équipe automate
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160930T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160930T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:93
DESCRIPTION:9h30-9h45 welcome\n\n9h45 Svetlana Puzynina\n10h15 Sebastian S
choener\n10h30 Célia Borlido\n11h Thibault Godin\n11h45 Benjamin Hellouin
\n12h15 Thomas Garrity\n\n14h Olivier Carton\n14h30 Sylvain Lombardy (LaBR
I)-- Démonstration du logiciel Vaucuson-R\n15h30 Pablo Rotondo
LOCATION:1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Is the right relaxation normal form for braids automatic? - Vincen
t Jugé\, LSV\, ENS de Cachan
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161028T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161028T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:111
DESCRIPTION:Representations of braids as isotopy classes of laminations of
\npunctured disks are related with a family of normal forms\, which we\nca
ll relaxation normal forms. Roughly speaking\, every braid is\nidentified
with a picture on a punctured disk\, and reducing\nstep-by-step the comple
xity of this picture amounts to choosing a\nrelaxation normal form of the
braid.\n\nWe will study the right relaxation normal form\, which belongs t
o this\nfamily of normal forms. We will show that it is regular\, and that
it\nis synchronously bi-automatic if and only if the braid group has 3\np
unctures or less.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:One Hierarchy Spawns Another: Graph Deconstructions and the Comple
xity Classification of Conjunctive Queries - Hubie Chen
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161007T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161007T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:112
DESCRIPTION:We study the classical problem of conjunctive query evaluation
. This problem admits multiple formulations and has been studied in numer
ous contexts\; for example\, it is a formulation of the constraint satisfa
ction problem\, as well as the problem of deciding if there is a homomorph
ism from one relational structure to another (which transparently generali
zes the graph homomorphism problem).\n\nWe here restrict the problem accor
ding to the set of permissible queries\; the particular formulation we wor
k with is the relational homomorphism problem over a class of structures A
\, wherein each instance must be a pair of structures such that the first
structure is an element of A. We present a comprehensive complexity classi
fication of these problems\, which strongly links graph-theoretic properti
es of A to the complexity of the corresponding homomorphism problem. In pa
rticular\, we define a binary relation on graph classes and completely des
cribe the resulting hierarchy given by this relation. This binary relation
is defined in terms of a notion which we call graph deconstruction and wh
ich is a variant of the well-known notion of tree decomposition. We then u
se this graph hierarchy to infer a complexity hierarchy of homomorphism pr
oblems which is comprehensive up to a computationally very weak notion of
reduction\, namely\, a parameterized form of quantifier-free reductions. W
e obtain a significantly refined complexity classification of left-hand si
de restricted homomorphism problems\, as well as a unifying\, modular\, an
d conceptually clean treatment of existing complexity classifications\, su
ch as the classifications by Grohe-Schwentick-Segoufin (STOC 2001) and Gro
he (FOCS 2003\, JACM 2007).\n\nAfter presenting this new advance\, we will
compare this line of research with another that aims to classify the comp
lexity of the homomorphism problem where the second (target) structure is
fixed\, and that is currently being studied using universal-algebraic meth
ods. We will also make some remarks on two intriguing variants\, injectiv
e homomorphism (also called embedding) and surjective homomorphism.\n\nThi
s talk is mostly based on joint work with Moritz Müller that appeared in
CSL-LICS ’14.\nIn theory\, the talk will be presented in a self-containe
d fashion\, and will not assume prior knowledge of any of the studied noti
ons.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Subword Based Abstractions of Formal Languages - Georg Zetzsche\,
LSV\, ENS de Cachan
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161021T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161021T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:113
DESCRIPTION:A successful idea in the area of verification is to consider\n
finite-state abstractions of infinite-state systems. A prominent\nexample
is the fact that many language classes satisfy a Parikh's\ntheorem\, i.e.
for each language\, there exists a finite automaton\nthat accepts the sam
e language up to the order of letters. Hence\,\nprovided that the abstract
ion preserves pertinent properties\,\nthis allows us to work with finite-s
tate systems\, which are much\neasier to handle.\n\nWhile Parikh-style abs
tractions have been studied very intensely\nover the last decades\, recent
years have seen an increasing\ninterest in abstractions based on the subw
ord ordering. Examples\ninclude the set of (non necessarily contiguous) su
bwords of\nmembers of a language (the downward closure)\, or their superwo
rds\n(the upward closure). Whereas it is well-known that these\nclosures
are regular for any language\, it is often not obvious\nhow to compute the
m. Another type of subword based abstractions\nare piecewise testable sep
arators. Here\, a separators acts as an\nabstraction of a pair of languag
es.\n\nThis talk will present approaches to computing closures\, deciding\
nseparability by piecewise testable languages\, and a (perhaps\nsurprising
) connection between these problems. If time permits\,\ncomplexity issues
will be discussed as well.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:One-Counter Automata with Counter Observability - Benedikt Bollig\
, LSV\, ENS de Cachan
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161125T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161125T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:114
DESCRIPTION:In a one-counter automaton (OCA)\, one can produce a letter fr
om some finite alphabet\, increment and decrement the counter by one\, or
compare it with constants up to some threshold. It is well-known that univ
ersality and language inclusion for OCAs are undecidable. In this paper\,
we consider OCAs with counter observability: Whenever the automaton produc
es a letter\, it outputs the current counter value along with it. Hence\,
its language is now a set of words over an infinite alphabet. We show that
universality and inclusion for that model are PSPACE-complete\, thus no h
arder than the corresponding problems for finite automata. In fact\, by es
tablishing a link with visibly one-counter automata\, we show that OCAs wi
th counter observability are effectively determinizable and closed under a
ll boolean operations.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alternating Two-way Two-tape Automata - Léo Exibard
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161014T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161014T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:124
DESCRIPTION:In this talk\, we study a model computing relations over finit
e words\, generalising one- and two-way transducers. The model\, called tw
o-way two-tape automaton\, consists in a finite-state machine with two rea
d-only tapes\, each one with a reading head able to go both ways.\nWe firs
t emphasize its relation with 4-way automata\, which recognize sets of two
-dimensional arrays of letters called picture languages\; such corresponde
nce provides a proof of the undecidability of the model\, and an example s
eparating determinism and non-determinism.\nWe then describe several techn
iques which\, applied to our model\, establish (non-)closure properties of
the recognizable relations.\nFinally\, the main result presented in this
talk is that alternating two-way two-tape automata are not closed under co
mplementation. The proof is a refinement of one of J. Kari for picture lan
guages.\n\nJoint work with Olivier Carton and Olivier Serre.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Towards an algebraic theory of rational word functions - Nathan Lh
ote\, LaBRI & ULB
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161118T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161118T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:126
DESCRIPTION:In formal language theory\, several different models character
ize regular languages\, such as finite automata\, congruences of finite in
dex\, or monadic second-order logic (MSO). Moreover\, several fragments of
MSO have effective characterizations based on algebraic properties\, the
most famous example being the Schützenberger-McNaughton and Papert theore
m linking first-order logic with aperiodic congruences.\nWhen we consider
transducers instead of automata\, such characterizations are much more cha
llenging\, because many of the properties of regular languages do not gene
ralize to regular word functions. In this paper we consider functions that
are definable by one-way transducers (rational functions). We show that t
he canonical bimachine of Reutenauer and Schützenberger preserves certain
algebraic properties of rational functions\, similar to the syntactic con
gruence for languages. In particular\, we give an effective characterizati
on of functions that can be defined by an aperiodic one-way transducer.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Workshop - Lia Infinis
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161104T092000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161104T102000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:130
DESCRIPTION:Program:\n *(09h20 - 09h30) Opening\n *(09h30 - 10h00) Serge
Grigorieff : "Algorithmic randomness and uniform distribution modulo one"
\n *(10h00 - 10h30) Stéphane Demri : "Reasoning about data repetitions w
ith counter systems"\n *(10h30 - 11h00) Coffee Break\n *(11h00 - 11h30)
Michel Habib : "A nice graph problem coming from biology: the study of rea
d networks"\n *(11h30 - 12h00) Delia Kesner : "Completeness of Call-by-Ne
ed (A fresh view)"\n *(12h00 - 12h30) Pierre Vial : "Infinite Intersectio
n Types as Sequences: a New Answer to Klop's Problem"\n *(12h30 - 14h00)
Lunch (Buffon Restaurant - 17 rue Hélène Brion - Paris 13ème)\n *(14h0
0 - 14h30) Verónica Becher : "Finite-state independence and normal sequen
ces"\n *(14h30 - 15h00) Brigitte Vallée : "Towards the random generation
of arithmetical objects"\n *(15h00 - 15h30) Valérie Berthé : "Dynamica
l systems and their trajectories"\n *(15h30 - 16h00) Coffee Break\n *(16
h00 - 16h30) Nicolás Alvarez : "Incompressible sequences on subshifts of
finite type"\n *(16h30 - 17h00) Eugene Asarin : "Entropy Games"\n *(17h0
0 - 18h00) Discussion about the future of LIA INFINIS\n\n[[https://www.iri
f.fr/~kesner/lia/workshop-lia-2016.html|More details are available here]].
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Some equational theories of labeled posets - Christian Choffrut\,
IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161202T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161202T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:141
DESCRIPTION:Joint work with Zoltán Ésik University of Szeged\, Hungary\n
\nWe equip the collection of labeled posets (partially ordered sets)\, \n
abbreviated l.p.\, with different operations:\n series product (concatena
tion of l.p)\, parallel \nproduct (disjoint union of posets)\, omega-po
wer (concatenation\nof an omega sequence of the same poset) and \nomega-pr
oduct (concatenation of an omega sequence of possibly different posets\,
\nwhich has therefore infinite arity).\nWe select four subsets of these op
erations and show that in each case \nthe equational theory is axiomatizab
le. We characterize \nthe free algebras in the corresponding varieties\,
both algebraically as classes which are closed \nunder the above operation
s as well as combinatorially as classes of partially ordered subsets. \nWe
also study the decidability issues when the question makes sense.\n\nNous
munissons la collection des posets étiquetés (ensembles partiellement)\
,\nen abrégé p.e.\, de différentes opérations:\nlproduit série (conc
aténation de p.e.)\, \nproduit parallèle (union disjointe de p.e.)\,
omega puissance (concaténation\nd'une omega suite du même p.e.) et \no
mega produit (concaténation d'une omega suite de p.e.\, \néventuelleme
nt différents\, donc d'arité infinie.\nNous distinguons quatre sous-ense
mbles parmi les opérations ci-dessus et nous montrons\nque dans chaque c
as la théorie équationnelle est axiomatisable. Nous caractérisons \nle
s algèbres libres dans les variétiés correspondante aussi bien algé
briquement en tant \nclasses d'algèbres fermées pour les opérations ci
-dessus et combinatoriquement \nen tant que classes de structures ordonné
es.\nNous étudions aussi les problèmes de décidabilité quand ils ont u
n sens.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing the entropy of mixing tilings - Benjamin Hellouin\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20161209T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20161209T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:158
DESCRIPTION:The entropy of a language is a measure of its complexity and a
well-studied dynamical invariant. I consider two related questions: for a
given class of languages\, can this parameter be computed\, and what valu
es can it take?\n\nIn 1D tilings (subshifts) of finite type\, we have know
n how to compute the entropy for 30 years\, and the method gives an algebr
aic characterisation of possible values. In higher dimension\, a surprise
came in 2007: not only is the entropy not computable in general\, but any
upper-semi-computable real number appears as entropy - a weak computationa
l condition. Since then new works have shown that entropy becomes computab
le again with aditionnal mixing hypotheses. We do not know yet where the b
order between computable and uncomputable lies.\n\nIn this talk\, I will e
xplore the case of general subshifts (not of finite type) in any dimension
\, hoping to shed some light on the finite type case. I relate the computa
tional difficulty of computing the entropy to the difficulty of deciding i
f a word belongs to the language. I exhibit a threshold in the mixing rate
where the difficulty of the problem jumps suddenly\, the very phenomenon
that is expected in the finite type case.\n\nThis is a joint work with Sil
vère Gangloff and Cristobal Rojas.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Logical characterization of Probabilistic Simulation and Bisimulat
ion. - Nathanaël Fijalkow\, Alan Turing Institute
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170120T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170120T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:163
DESCRIPTION:I will discuss a notion of equivalence between two probabilist
ic systems introduced by Larsen and Skou in 89 called probabilistic bisimu
lation.\n\nIn particular\, I will look at logical characterizations for th
is notion: the goal is to describe a logic such that two systems are bisim
ilar if and only if they satisfy the same formulas. This question goes all
the way back to Hennessey and Millner for non probabilistic transition sy
stems.\n\nI will develop topological tools and give very general logical c
haracterization results for probabilistic simulation and bisimulation.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Schema Mappings for Data Graphs - Nadime Francis\, University of E
dinburgh
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170127T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170127T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:164
DESCRIPTION:Schema mappings are a fundamental concept in data integration
and\nexchange\, and they have been thoroughly studied in different data\nm
odels. For graph data\, however\, mappings have been studied in a very\nre
stricted context that\, unlike real-life graph databases\, completely\ndis
regards the data they store. Our main goal is to understand query\nansweri
ng under graph schema mappings - in particular\, in exchange and\nintegrat
ion of graph data - for graph databases that mix graph\nstructure with dat
a. We show that adding data querying alters the\npicture in a very signifi
cant way.\n\nAs the model\, we use data graphs: a theoretical abstraction
of\nproperty graphs employed by graph database implementations. We start\n
by showing a very strong negative result: using the simplest form of\nnont
rivial navigation in mappings makes answering even simple queries\nthat mi
x navigation and data undecidable. This result suggests that\nfor the purp
oses of integration and exchange\, schema mappings ought to\nexclude recur
sively defined navigation over target data. For such\nmappings and analogs
of regular path queries that take data into\naccount\, query answering be
comes decidable\, although intractable. To\nrestore tractability without i
mposing further restrictions on queries\,\nwe propose a new approach based
on the use of null values that\nresemble usual nulls of relational DBMSs\
, as opposed to marked nulls\none typically uses in integration and exchan
ge tasks. If one moves\naway from path queries and considers more complex
patterns\, query\nanswering becomes undecidable again\, even for the simpl
est possible\nmappings.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Extended symmetries of some higher dimensional shift spaces. - Ree
m Yassawi\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170113T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170113T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:171
DESCRIPTION:Let $(X\,T)$ be a one-dimensional invertible subshift. The //s
ymmetry// group of $(X\,T)$ is the group of all shift-commuting homeomorp
hisms $X$. In the larger \n//reversing// symmetry group of $(X\,T)$\, we a
lso consider homeomorphisms $\\Phi$ of $X$ where $\\Phi \\circ T= T^{-1}\\
circ \\Phi$\, also called //lip conjugacies//. We define a generalisation
of the reversing symmetry\ngroup for higher dimensional shifts\, and we f
ind this //extended// symmetry group for two prototypical higher dimensio
nal shifts\, namely the chair substitution shift and the Ledrappier shift.
Joint work with M. Baake and J.A.G Roberts. \\\\\n––––– \\\\\n*
*French version:** //Les automorphismes généralisés des sous shifts.//
\\\\\nSoit $(X\,\\mathbb Z^d)$ un soushift inversible. Nous définissons l
e groupe des //automorphismes généralisés//: c'est le normalisateur d
u groupe engendré par le shift dans le groupe d'homéomorphismes de $X$.
Nous trouvons les automorphismes généralisés de deux shifts prototyiqu
es: le pavage de la chaise et le soushift Ledrappier. En collaboration ave
c M. Baake et J.A.G Roberts.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Query enumeration and Nowhere-dense graphs - Alexandre Vigny\, IMJ
-PRG
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170106T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170106T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:172
DESCRIPTION:The evaluation of queries is a central problem in database man
agement systems. Given a\nquery q and a database D the evaluation of q ove
r D consists in computing the set q(D) of all\nanswers to q on D. An inter
esting case is when the query is boolean (aka the model checking\nproblem\
, where the answer to the query is either a “yes” or a “no”). Even
for boolean query\,\nthe problem of computing the answer (with input q an
d D) is already PSpace-complete.\nFor non-boolean queries\, the size of th
e output can blow up to |D|^r\, where r is the arity of q.\nIt is therefor
e not always realistic to compute the entire set of solutions. Moreover\,
the\ntime needed to construct the set might not reflect the difficulty of
the task.\n\nIn this talk we will discuss query enumeration\, that is outp
utting the solutions one by one.\nTwo parameters enter in play\, the delay
and the preprocessing time. The delay is the maximal time\nbetween two co
nsecutive output and the preprocessing time is the time needed to produce
the first solution.\nWe will investigate cases where the delay is constant
(does not depend on the size of the database) and the\npreprocessing is l
inear (in the size of the database) i.e. constant delay enumeration after
linear preprocessing.\nThis is not always possible as this implies a linea
r model-checking. We will therefore add restriction\nto the classes of dat
abases and/or queries such as bounded degree databases\, tree-like structu
res\, conjunctive queries...
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Non-commutative lower bounds - Guillaume Lagarde\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170303T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170303T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:181
DESCRIPTION:No knowledge in arithmetic complexity will be assumed.\n\nWe s
till don't know an explicit polynomial that requires non-commutative circu
its of size at least superpolynomial.\nHowever\, the context of non commut
ativity seems to be convenient to get such lower bound because the rigidit
y of the non-commutativity implies a lot of constraints about the ways to
compute.\nIt is in this context that Nisan\, in 1991\, provides an exponen
tial lower bound against the non commutative Algebraic Branching Programs
computing the permanent\, the very first one in arithmetic complexity. We
show that this result can be naturally seen as a particular case of a theo
rem about circuits with //unique parse tree//\, and show some extensions t
o get closer to lower bounds for general NC circuits.\n\nTwo joint works:
with Guillaume Malod and Sylvain Perifel\; with Nutan Limaye and Srikanth
Srinivasan.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Quantifiers on languages and topological recognisers - Daniela Pet
risan\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170224T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170224T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:191
DESCRIPTION:In the first part of the talk I will recall the duality approa
ch to language recognition. To start with\, I will explain the following s
imple fact. The elements of the syntactic monoid of a regular language $L$
over a finite alphabet $A$ are in one to one correspondence with the ato
ms of the finite sub-Boolean algebra of $P(A^*)$ generated by the quotient
s of $L$. This correspondence can be seen as an instance of Stone duality
for Boolean algebras\, and has lead to a topological notion of recognition
for non-regular languages\, the so called Boolean spaces with internal mo
noids.\n\nA fundamental tool in studying the connection between algebraic
recognisers\, say classes of monoids\, and fragments of logics on words
is the availability of constructions on monoids which mirror the action of
quantifiers\, such as block products or other kinds of semidirect product
s. In the second part of the talk I will discuss generalisations of these
techniques beyond the case of regular languages and present a general rec
ipe for obtaining constructions on the topological recognisers introduced
above that correspond to operations on languages possibly specified by tra
nsducers.\n\nThis talk is based on joint work with Mai Gehrke and Luca Reg
gio.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Synchronisation d'automates aléatoires - Cyril Nicaud\, LIGM
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170331T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170331T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:193
DESCRIPTION:Il y a 50 ans\, Cerny a posé une conjecture combinatoire sur
les automates\, qui n'est toujours pas résolue. Un automate est dit synch
ronisé quand il existe un mot u et un état p tel que depuis n'importe qu
el état\, si on lit u on arrive en p. Sa conjecture est que si l'automate
synchronisé possède n états\, alors il existe un tel u de longueur au
plus (n-1)2. Dans cet exposé\, nous nous intéresserons à la version pro
babiliste de la conjecture de Cerny : on montrera qu'un automate aléatoir
e est non seulement synchronisé (résultat déjà prouvé par Berlinkov)\
, mais qu'en plus la conjecture de Cerny est vraie avec forte probabilité
.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Additive combinatorics generated by uniformly recurrent words - Sv
etlana Puzynina\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170217T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170217T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:194
DESCRIPTION:A subset of natural numbers is called an IP-set if it contains
an infinite increasing sequence of numbers and all its finite sums. In th
e talk we show how certain families of uniformly recurrent words can be us
ed to generate IP-sets\, as well as sets possessing some related additive
properties.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:An efficient algorithm to decide the periodicity of $b$-recognisab
le sets using MSDF convention - Victor Marsault\, University of Liège
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170310T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170310T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:197
DESCRIPTION:Given an integer base $b>1$\, a set of integers is represented
in base $b$\nby a language over $\\{0\,1\,\\dots\,b-1\\}$. The set is sa
id $b$-recognisable if\nits representation is a regular language. It is k
nown that eventually\nperiodic sets\nare $b$-recognisable in every base $b
$\, and Cobham's theorem imply the\nconverse: no other set is $b$-recognis
able in every base $b$.\n\nWe are interested in deciding whether a $b$-rec
ognisable set of integers\n(given as a finite automaton) is eventually per
iodic. Honkala showed\nin 1986 that this problem is decidable and recent
developments give\nefficient decision algorithms. However\, they only wor
k when the\nintegers are written with the least significant digit first.\n
\nIn this work\, we consider here the natural order of digits (Most\nSigni
ficant Digit First) and give a quasi-linear algorithm to solve\nthe proble
m in this case.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Asynchronous Distributed Automata: A Characterization of the Modal
Mu-Fragment - Fabian Reiter\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170317T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170317T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:208
DESCRIPTION:I will present the equivalence between a class of asynchronous
distributed automata and a small fragment of least fixpoint logic\, when
restricted to finite directed graphs. More specifically\, the considered l
ogic is (a variant of) the fragment of the modal μ-calculus that allows l
east fixpoints but forbids greatest fixpoints. The corresponding automaton
model uses a network of identical finite-state machines that communicate
in an asynchronous manner and whose state diagram must be acyclic except f
or self-loops. As a by-product\, the connection with logic also entails th
at the expressive power of those machines is independent of whether or not
messages can be lost.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Continuity & Transductions\, a theory of composability - Michaël
Cadilhac\, U. Tübingen
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170602T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170602T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:210
DESCRIPTION:Formal models for the computation of problems\, say circuits\,
automata\, Turing\nmachines\, can be naturally extended to compute word-t
o-word functions. But\nabstracting from the computation model\, what does
it mean to "lift" a language\nclass to functions? We propose to address
that question in a first step\,\ndeveloping a robust theory that incidenta
lly revolves around the (topological)\nnotion of continuity. In language-
theoretic terms\, a word-to-word function is\nV-continuous\, for a class o
f languages V\, if it preserves membership in V by\ninverse image.\n\nIn a
second step\, we focus on transducers\, i.e.\, automata with letter outpu
t.\nWe study the problem of deciding whether a given transducer realizes a
\nV-continuous function\, for some classical classes V (e.g.\, aperiodic l
anguages\,\ngroup languages\, piecewise-testable\, ...).\n\nIf time allows
\, we will also see when there exists a correlation between the\ntransduce
r structure (i.e.\, its transition monoid)\, and its computing a\ncontinuo
us function.\n\nJoint work with Olivier Carton\, Andreas Krebs\, Michael L
udwig\, Charles Paperman.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Des automates cellulaires unidirectionnels permutifs et du problè
me de la finitude pour les groupes d'automates. - Martin Delacourt\, U. Or
léans
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170324T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170324T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:221
DESCRIPTION:On s'intéresse au parallèle entre 2 problèmes sur des modè
les distincts d'automates. D'une part\, les automates de Mealy (transducte
urs lettre à lettre complets) qui produisent des semi-groupes engendrés
par les transformations sur les mots infinis associées aux états. En 201
3\, Gillibert a montré que le problème de la finitude de ces semi-groupe
s était indécidable\, en revanche la question est ouverte dans le cas o
ù l'automate de Mealy produit un groupe. D'autre part\, les automates cel
lulaires unidirectionnels pour lesquels la question de la décidabilité d
e la périodicité est ouverte. On peut montrer l'équivalence de ces prob
lèmes. On fera un pas vers une preuve d'indécidabilité en montrant qu'i
l est possible de simuler du calcul Turing dans un automate cellulaire uni
directionnel réversible\, rendant ainsi des problèmes de prédiction ind
écidables ainsi que la question de la périodicité partant d'une configu
ration donnée finie.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Automatic presentations for algebraic and relational structures -
Alan J. Cain\, U. Nova Lisbon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170407T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170407T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:224
DESCRIPTION:An automatic presentation (also called an FA-presentation) is
a\ndescription of a relational structure using regular languages. The\ncon
cept an FA-presentation arose in computer science\, to fulfil a need\nto e
xtend finite model theory to infinite structures. Informally\, an\nFA-pres
entation consists of a regular language of abstract\nrepresentatives for t
he elements of the structure\, such that each\nrelation (of arity $n$\, sa
y) can be recognized by a synchronous\n$n$-tape automaton. An FA-presentat
ion is "unary" if the language of\nrepresentatives is over a 1-letter alph
abet.\n\nIn this talk\, I will introduce and survey automatic presentation
s\,\nwith particular attention to connections with decidability and logic.
\nI will then discuss work with Nik Ruskuc (Univ. of St Andrews\, UK) and\
nRichard Thomas (Univ. of Leicester\, UK) on algebraic and combinatorial\n
structures that admit automatic presentations or unary automatic\npresenta
tions. The main focus will be on results that characterize the\nstructures
of some type (for example\, groups\, trees\, or partially\nordered sets)
that admit automatic presentations.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Symbolic dynamics and simulation theorems - Sebastián Barbieri\,
ENS Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170505T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170505T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:232
DESCRIPTION:In this talk I will give a gentle introduction to symbolic dyn
amics and motivate an open question in this field: which are the structure
s where can we construct aperiodic tilings using local rules. I will then
introduce the notion of simulation of an effective dynamical system and sh
ow how these results can be used to produce aperiodic tilings in extremely
complicated structures. We end the talk by presenting a novel simulation
theorem which allows to show the existence of such tilings in the Grigorch
uk group.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Recognizability for sequences of morphisms - Wolfgang Steiner\, IR
IF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170421T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170421T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:238
DESCRIPTION:We investigate different notions of recognizability for a free
monoid morphism $\\sigma: A^* \\to B^*$. Full recognizability occurs when
each (aperiodic) two-sided sequence over $B$ admits at most one tiling wi
th words $\\sigma(a)$\, $a \\in A$. This is stronger than the classical no
tion of recognizability of a substitution $\\sigma$\, where the tiling mus
t be compatible with the language of the substitution. We show that if $A$
is a two-letter alphabet\, or if the incidence matrix of $\\sigma$ has ra
nk $|A|$\, or if $\\sigma$ is permutative\, then $\\sigma$ is fully recogn
izable. Next we investigate the classical notion of recognizability and im
prove earlier results of Mossé (1992) and Bezuglyi\, Kwiatkowski and Medy
nets (2009)\, by showing that any substitution is recognizable for aperiod
ic points in its substitutive shift. Finally we define (eventual) recogniz
ability for sequences of morphisms which define an $S$-adic shift. We prov
e that a sequence of morphisms on alphabets of bounded size\, such that co
mpositions of consecutive morphisms are growing on all letters\, is eventu
ally recognizable for aperiodic points. We provide examples of eventually
recognizable\, but not recognizable\, sequences of morphisms\, and sequenc
es of morphisms which are not eventually recognizable. As an application\,
for a recognizable sequence of morphisms\, we obtain an almost everywhere
bijective correspondence between the $S$-adic shift it generates and the
measurable Bratteli-Vershik dynamical system that it defines.\n\nThis is j
oint work with Valérie Berthé\, Jörg Thuswaldner and Reem Yassawi.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Higher computability and Randomness - Paul-Elliot Anglès D'auriac
\, LACL
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170512T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170512T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:252
DESCRIPTION:Several notions of computability have been defined before ever
y one agreed that Turing Machines are the good model of computation\, a st
atement raised to the widely accepted Church-Turing Thesis.\nHowever\, sin
ce then\, lots of stronger computability notions have been defined and stu
died\, for the sake of math and because it gives us new insight on some al
ready existing fields.\n\nIn this talk\, we will see two ways to extend us
ual computability: by defining a more powerful model\, or in a more set th
eoretic fashion. The first method is used to define Infinite Time Turing M
achine\, a model where Turing Machines are allowed to compute throught inf
inite time (that is\, throught the ordinals instead of the integers). It h
as a lot of links with admissibility theory. The second method is used to
define alpha-recursion\, where alpha is any admissible ordinal. It is an a
bstract and very general definition of computation. Even if it has a very
set-theoretic basis\, it reflects the idea of computation and contains the
notions of Turing Machine and Infinite Time Turing Machines computabiliti
es. It also includes Higher Computability.\n\nBy investigating which prope
rties on the extensions are needed to lift theorems to the new setting\, w
e are able to isolate the important properties of the classical case. We a
lso apply these generalized recursion theories to define randomness\, in t
he same way that we did in the classical case: a string is said to be rand
om if it has no exceptionnal properties\, in a computable sense. Our new d
efinition of computation then gives use new definition of randomness.\n\n(
No prior knowledge on set theory is assumed.)
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Small complexity classes for cellular automata\, dealing with diam
ond and round neighborhood - Anaël Grandjean\, LIRMM
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170519T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170519T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:256
DESCRIPTION:We are interested in 2-dimensional cellular automata and more
precisely in the recognition of langages in small time. The time complexit
y we consider is called real-time and is rather classic for the study of c
ellular automata. It consists of the smallest amount of time needed to rea
d the whole imput. It has been shown that this set of langages depend on t
he neighborhood of the automaton. For example the two most used neighborho
ods (Moore and von Neumann ones) are different with respect to this comple
xity. Our study deals with more generic sets of neighborhoods\, round and
diamond neighborhoods. We prove that all diamond neighborhoods can recogni
ze the same langages in real time and that the round neighborhoods can rec
ognize stricly less than the diamond ones.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Invariant Synthesis for Linear Dynamical Systems - Pierre Ohlmann\
, ENS de Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170609T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170609T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:257
DESCRIPTION:The Orbit Problem consists of determining\, given a linear tra
nsformation $A$ on $Q^d$\, together with vectors $x$ and $y$\, whether the
orbit of $x$ under repeated applications of $A$ can ever reach $y$.\n\nWe
will investigate this problem with a different point of view: is it possi
ble to synthesise suitable invariants\, that is\, subsets of $Q^d$ that co
ntain $x$ but not $y$. Such invariants provide natural certificates for ne
gative instances of the Orbit Problem. We will show that semialgebraic inv
ariants exist in all reasonable cases. A more recent (yet unpublished) res
ult is that existence of semilinear invariants is decidable.\n\nThis is a
joint work with Nathanaël Fijalkow\, Joël Ouaknine\, Amaury Pouly and Ja
mes Worrell\, published in STACS 2017.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Classifying real numbers using continued fractions and thermodynam
ics. - Thomas Garrity
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170616T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170616T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:266
DESCRIPTION:A new classification scheme for real numbers will be given\, m
otivated by ideas from statistical mechanics in general and work of Knauf
and Fiala and Kleban in particular. Critical for this classification of
real numbers will be the Diophantine properties of continued fraction exp
ansions. Underneath this classification is a new partition function on th
e space of infinite sequences of zeros and ones.
LOCATION:Salle 1006
END:VEVENT
BEGIN:VEVENT
SUMMARY:Analyse Quantitative des Systèmes Stochastiques - Jeux de Priorit
é et Population de Chaînes de Markov (soutenance de thèse) - Bruno Kare
lović\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170707T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170707T150000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:285
DESCRIPTION:
LOCATION:0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:Automates\, (semi)groupes et dualités (soutenance d'habilitation)
- Matthieu Picantin\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170710T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170710T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:287
DESCRIPTION:Dans le cadre des journées de clôture du projet MealyM (http
s://mealym.sciencesconf.org/)\n\nManuscrit disponible ici : \nhttps://meal
ym.sciencesconf.org/data/program/HdR.pdf
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mealy machines\, automaton (semi)groups\, decision problems\, and
random generation (PhD defence) - Thibault Godin\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20170713T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20170713T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:288
DESCRIPTION:Dans le cadre des journées de clôture du projet MealyM (http
s://mealym.sciencesconf.org/)\n\nManuscrit disponible ici : \nhttps://www.
irif.fr/_media/users/godin/these30-06-17.pdf
LOCATION:Amphi Turing
END:VEVENT
BEGIN:VEVENT
SUMMARY:Comparing the speed of semi-Markov decision processes - Nahtanaël
Fijalkow\, University College London
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171006T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171006T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:314
DESCRIPTION:A Markov decision process models the interactions between a co
ntroller giving inputs and a stochastic environment. In this well-studied
model\, transitions are fired instantaneously. \nWe study semi-Markov deci
sion processes\, where each transition takes some time to fire\, determine
d by a given probabilistic distribution (for instance\, an exponential dis
tribution). The question we investigate is how to compare two semi-Markov
decision processes. We introduce and study the algorithmic complexity of t
wo relations\, "being faster than"\, and "being equally fast as".
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Completely reachable automata: an interplay between semigroups\, a
utomata\, and trees - Mikhail V. Volkov\, Ural Federal University\, Russie
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171027T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171027T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:318
DESCRIPTION:We present a few results and several open problems concerning
complete deterministic finite automata in which every non-empty subset of
the state set occurs as the image of the whole state set under the action
of a suitable input word. In particular\, we give a complete description o
f such automata with minimal transition monoid size.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lempel-Ziv: a "one-bit catastrophe" but not a tragedy - Sylvain Pe
rifel\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171020T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171020T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:327
DESCRIPTION:The robustness of the famous compression algorithm of Lempel a
nd Ziv is still not well understood: in particular\, until now it was unkn
own whether the addition of one bit in front of a compressible word could
make it incompressible. This talk will answer that question\, advertised b
y Jack Lutz under the name "one-bit catastrophe" and which has been around
since at least 1998. We will show that a "well" compressible word remains
compressible when a bit is added in front of it\, but some "few" compress
ible words indeed become incompressible.\nThis is a joint work with Guilla
ume Lagarde.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Max-plus automata and tropical identities - Laure Daviaud\, Univer
sity of Warwick
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171110T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171110T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:328
DESCRIPTION:In this talk I will discuss the following natural question:\nG
iven a class of computational models C\, does there exist two distinct inp
uts which give the same output for all the models in the class.\nI will di
scuss this question more precisely for weighted automata in general and fo
r max-plus automata in particular. Weighted automata are a quantitative ex
tension of automata which allows to compute values such as costs and proba
bilities. Max-plus automata are a special case of weighted automata\, part
icularly suitable to model gain optimisation problems.\nWe will see that i
n this last case\, we end up with particularly intricate (and open) questi
ons\, related to finding identities in the semiring of tropical matrices.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Randomness and uniform distribution modulo one - Verónica Becher\
, Universidad de Buenos Aires and CONICET
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180119T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180119T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:346
DESCRIPTION:How is algorithmic randomness related to the classical theory
of uniform distribution? In this talk we consider the definition of Martin
-Löf randomness for real numbers in terms of uniform distribution of seq
uences. We present a necessary condition for a real number to be Martin-L
öf random\, and a strengthening of that condition which is sufficient fo
r Martin-Löf randomness. For this strengthening we define a notion of uni
form distribution relative to the computably enumerable open subsets of th
e unit interval. We call the notion Sigma^0_1-uniform distribution.\n\nThi
s is joint work with Serge Grigorieff and Theodore Slaman.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nash equilibria in games on graphs with public signal monitoring -
Patricia Bouyer\, LSV\, CNRS et ENS Cachan
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171201T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171201T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:352
DESCRIPTION:We study Nash equilibria in games on graphs with an imperfect
monitoring based on a public signal. In such games\, deviations and player
s responsible for those deviations can be hard to detect and track. We pro
pose a generic epistemic game abstraction\, which conveniently allows to r
epresent the knowledge of the players about these deviations\, and give a
characterization of Nash equilibria in terms of winning strategies in the
abstraction. We then use the abstraction to develop algorithms for some pa
yoff functions.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pomset languages and concurrent Kleene algebras - Paul Brunet\, Un
iversity College London
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171124T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171124T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:354
DESCRIPTION:Concurrent Kleene algebras (CKA) and bi-Kleene algebras suppor
t equational reasoning about computing systems with concurrent behaviours.
Their natural semantics is given by series(-parallel) rational pomset lan
guages\, a standard true concurrency semantics\, which is often associated
with processes of Petri nets.\n \nIn the first part of the talk\, I will
present an automaton model designed to describe such languages of pomset\,
which satisfies a Kleene-like theorem. The main difference with previous
constructions is that from expressions to automata\, we use Brzozowski der
ivatives.\n \nIn a second part\, I will use Petri nets to reduce the probl
em of containment of languages of pomsets to the equivalence of finite sta
te automata. In doing so\, we prove decidabilty as well as provide tight c
omplexity bounds.\n \nI will finish the presentation by briefly presenting
a recent proof of completness\, showing that two series-rational expressi
ons are equivalent according to the laws of CKA exactly when their pomset
semantics are equal.\n \nJoint work with Damien Pous\, Georg Struth\, Tobi
as Kappé\, Bas Luttik\, Alexandra Silva\, and Fabio Zanasi
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing and explaining ontology-mediated query answers over inco
nsistent data - Camille Bourgaux\, Télécom ParisTech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171208T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171208T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:355
DESCRIPTION:The problem of querying description logic knowledge bases usin
g database-style queries (in particular\, conjunctive queries) has been a
major focus of recent description logic research. An important issue that
arises in this context is how to handle the case in which the data is inco
nsistent with the ontology. Indeed\, since in classical logic an\ninconsis
tent logical theory implies every formula\, inconsistency-tolerant semanti
cs are needed to obtain meaningful answers.\nI will first present a practi
cal approach for querying inconsistent DL-Lite knowledge bases using three
natural semantics (AR\, IAR\, and brave) previously proposed in the liter
ature and that rely on the notion of a repair\, which is an inclusion-maxi
mal subset of the data consistent with the ontology. Since these three sem
antics provide answers with different levels of confidence\, I will then p
resent a framework for explaining query results\, to help the user to unde
rstand why a given answer was or was not obtained under one of the three s
emantics.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:Deciding complexity of languages via games - Michał Skrzypczak\,
University of Warsaw
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171117T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171117T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:360
DESCRIPTION:My presentation is about effective characterisations: given\na
representation of a regular language\, decide if the language is\n"simple
" in some specific sense. A classical example of such a\ncharacterisation
is the result by Schutzenberger\, McNaughton\, and\nPapert\, saying that i
t is decidable if a given regular language of\nfinite words can be defined
in first-order logic. Over the years\, such\ncharacterisations were provi
ded for many other natural classes of\nlanguages\, especially in the case
of finite and infinite words. It is\noften assumed that a "golden standard
" for such a characterisation\nis to provide equations that must be satisf
ied in a respective algebra\nrepresenting the language.\n\nThe aim of my t
alk is to survey a number of examples in which it is\nnot possible to prov
ide algebraic representation of the considered\nlanguages\; but instead ch
aracterisations can be obtained by a\nwell-designed game of infinite durat
ion. Using these examples\, I will\ntry to argue that game-based approach
is the natural replacement for\nalgebraic framework in the cases where alg
ebraic representations are\nnot available.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Anna-Carla Rousso\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160311T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160311T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:385
DESCRIPTION:
LOCATION:Salle 0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:La Tour d'Hanoï\, revue par Dudeney - Thierry Bousch\, Paris Sud
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160304T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160304T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:386
DESCRIPTION:
LOCATION:Salle 0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Laurent Bartholdi\, ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160122T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160122T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:387
DESCRIPTION:
LOCATION:Salle 0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:Factorability structures - Viktoriya Ozornova\, Universität Breme
n
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160115T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160115T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:388
DESCRIPTION:
LOCATION:Salle 0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:Provenance Circuits for Trees and Treelike Instances - Antoine Ama
rilli\, Télécom ParisTech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160108T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160108T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:389
DESCRIPTION:
LOCATION:Salle 0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:[[http://mps2016.labri.fr/index_fr.html|Programme]] - Colloque En
L'honneur De Marcel-Paul Schützenberger (21-25/03/2016)
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20160321T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20160321T110000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:396
DESCRIPTION:
LOCATION:LABRI
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sparsity and Stability - Szymon Toruńczyk\, MIMUW
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180202T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180202T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:448
DESCRIPTION:Nowhere dense graph classes\, introduced by Nesetril and Osson
a de Mendez\, are a broad family of sparse graph classes for which many al
gorithmic problems which are hard in general become tractable.\nIn particu
lar\, model checking first-order logic is fixed-parameter tractable over s
uch classes\, as shown recently by Grohe\, Kreutzer\, and Siebertz. With t
he aim of finding generalizations of this result to dense graph classes\,
I will talk about some recent developments in the study of the connections
between nowheredenseness and stability (developed by Shelah).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Algorithmic Complexity of Well-Quasi-Orders - Sylvain Schmitz\, LS
V
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180209T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180209T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:524
DESCRIPTION:The talk will be based on my habilitation defense talk from No
v. 27 2018\, which was dedicated to the algorithmic complexity of well-qua
si-orders. The latter find applications in verification\, where they allo
w to tackle systems featuring an infinite state-space\, representing for i
nstance integer counters\, the number of active threads in concurrent sett
ings\, real-time clocks\, call stacks\, cryptographic nonces\, or the cont
ents of communication channels.\n\nThe talk gives an overview of the compl
exity questions arising from the use of well-quasi-orders\, including the
definition of complexity classes suitable for problems with non-elementary
complexity and proof techniques for upper bounds. I will mostly focus on
the ideas behind the first known complexity upper bound for reachability
in vector addition systems and Petri nets.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A canonical form for weighted automata and applications to approxi
mate minimization - Prakash Panangaden\, McGill University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180216T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180216T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:526
DESCRIPTION:We study the problem of constructing approximations to a weigh
ted automaton. Weighted finite automata (WFA) are closely related to the t
heory of rational series. A rational series is a function from strings to
real numbers that can be computed by a WFA. This includes probability dis
tributions generated by hidden Markov models and probabilistic automata. T
he relationship between rational series and WFA is analogous to the relati
onship between regular languages and ordinary automata. Associated with su
ch rational series are infinite matrices called Hankel matrices which play
a fundamental role in the theory of minimal WFA. In this talk I describe
: (1) an effective procedure for computing the singular value decompositio
n (SVD) of such infinite Hankel matrices based on their finite representat
ion in terms of WFA\; (2) a new canonical form for WFA based on this SVD d
ecomposition\; and\, (3) an algorithm to construct approximate minimizatio
ns of a given WFA. The goal of the approximate minimization algorithm is t
o start from a minimal WFA and produce a smaller WFA that is close to the
given one in a certain sense. The desired size of the approximating automa
ton is given as input. I will give bounds describing how well the approxim
ation emulates the behavior of the original WFA.\n\nThis is joint work wit
h Borja Balle and Doina Precup and was presented at LICS 2015 in Kyoto.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Graph Exploration: Graph Search made Easy - Davide Mottin\, Hasso
Platner Institute
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180420T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180420T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:539
DESCRIPTION:The increasing interest in social networks\, knowledge graphs\
, protein-interaction\, and many other types of networks has raised the qu
estion how users can explore such large and complex graph structures easil
y. \nIn this regard\, graph exploration has emerged as a complementary too
lbox for graph management\, graph mining\, or graph visualization in which
the user is a first class citizen. \nGraph exploration combines and expan
ds database\, data mining\, and machine learning approaches with the user
eye on one side and the system perspective on the other. \n\nThe talk show
s how graph exploration can considerably support any analysis on graphs in
a fresh and exciting manner\, by combining interactive methods\, personal
ized results\, adaptive structures\, and scalable algorithms. \nI describe
the recent efforts for a graph exploration stack which supports interacti
vity\, personalization\, adaptivity\, and scalability through intuitive an
d efficient techniques we recently proposed.\nThe current methods show enc
ouraging results in reducing the effort of experts and novice users in fin
ding the information of interests through example-based approaches\, perso
nalized summaries\, and active learning theories. \nFinally\, I present th
e vision for the future in graph exploration research and show the chief c
hallenges in databases\, data analysis\, and machine learning.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Formal semantics of the query-language Cypher - Victor Marsault\,
LFCS\, University of Edinburgh
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180406T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180406T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:541
DESCRIPTION:Cypher is a query-language for property-graphs. It was origin
ally\ndesigned and implemented as part of the Neo4j graph database\, and i
t\nis currently used by several commercial database products and\nresearch
ers. The semantics of Cypher queries is currently described\nusing natura
l language and\, as a result\, it is often not well defined.\nThis work is
part of a project to define a full denotational semantics\nof Cypher quer
ies. The talk will first present the main features of\nCypher through exa
mples\, including the core mecanism: graph\npattern-matching\, and then wi
ll describe the principle of the\nformal semantics.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:One Theorem to Rule Them All: A Unified Translation of LTL into om
ega-Automata - Javier Esparza\, Technical University of Munich
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180323T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180323T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:555
DESCRIPTION:We present a unified translation of LTL formulas into determin
istic Rabin automata\, limit-deterministic Büchi automata\, and nondeterm
inistic Büchi automata. The translations yield automata of asymptotically
optimal size (double or single exponential\, respectively). All three tra
nslations are derived from one single Master Theorem of purely logical nat
ure. The Master Theorem decomposes the language of a formula into a positi
ve boolean combination of languages that can be translated into omega-auto
mata by elementary means. In particular\, the breakpoint\, Safra\, and ran
king constructions used in other translations are not needed.\n\nJoint wor
k with Jan Kretinsky and Salomon Sickert.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Width of non-deterministic automata - Denis Kuperberg\, ÉNS Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180413T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180413T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:556
DESCRIPTION:The issue of determinism versus non-determinism is central in
computer science. In order to better understand this gap\, the intermediar
y model of Good-for-Games (GFG) automata is currently being explored in it
s various aspects. A GFG automaton is a non-deterministic automaton on fin
ite or infinite words\, where accepting runs can be built on-the-fly on va
lid input words. I will recall recent advances on this model\, and describ
e a newly introduced generalisation: width. The width of an automaton can
be viewed as a measure of its amount of nondeterminism. Width generalises
the notion of GFG automata\, which correspond to NFAs of width 1. I will d
escribe how GFG or deterministic automata can be built from non-determinis
tic automata\, with width being a crucial parameter in the construction. I
will finally mention results and open problems related to the computation
al complexity of computing GFGness or width of automata.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Extension pondérée des logiques modales dans le cadre des croyan
ces graduelles - Bénédicte Legastelois\, LIP6
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180330T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180330T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:571
DESCRIPTION:La formalisation et le raisonnement sur des notions non-vérif
onctionnelles\, telles que la croyance\, le savoir ou la certitude\, sont
des enjeux actuels de l'intelligence artificielle. Ces notions peuvent men
er à représenter et évaluer des informations subjectives et sont\, en p
articulier\, formalisées en logique modale. Motivés par la modélisation
du raisonnement sur les croyances graduelles\, dont l'expressivité est e
nrichie par rapport aux croyances classiques\, mes travaux portent sur les
extensions pondérées des logiques modales.\n\nDans le cadre général d
es logiques modales\, je propose d'abord une sémantique proportionnelle p
our des opérateurs modaux pondérés\, basée sur des modèles de Kripke
classiques. J'étudie ensuite la définition d'axiomes modaux pondérés
étendant les axiomes classiques et propose une typologie les répartissan
t en quatre catégories\, selon l'enrichissement du cas classique qu'ils p
roduisent et leur correspondance avec la contrainte associée sur la relat
ion d'accessibilité.\n\nD'autre part\, je m'intéresse à une formalisati
on des croyances graduelles\, basée sur la conception représentationalis
te des croyances et reposant sur un modèle ensembliste flou. J'en étudie
plusieurs aspects\, comme les propriétés arithmétiques et l'applicatio
n de la négation.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Congruence preservation\, treillis et reconnaissabilite - Irène G
uessarian\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180518T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180518T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:592
DESCRIPTION:Looking at some monoids and (semi)rings (natural numbers\, int
egers and p- adic integers)\, and more generally\, residually finite algeb
ras (in a strong sense)\, we prove the equivalence of two ways for a funct
ion on such an algebra to behave like the operations of the algebra. The f
irst way is to preserve congruences or stable preorders. The second way is
to demand that preimages of recognizable sets belong to the lattice or th
e Boolean algebra generated by the preimages of recognizable sets by “de
rived unary operations” of the algebra (such as trans- lations\, quotien
ts\,. . . ).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Groups generated by bireversible Mealy automata: a combinatorial e
xplosion - Ines Klimann\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180601T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180601T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:593
DESCRIPTION:The study on how (semi)groups grow has been highlighted since
Milnor's\nquestion on the existence of groups of intermediate growth (fast
er\nthan any polynomial and slower than any exponential) in 1968. A very\n
first example of such a group was given by Grigorchuk in 1983 in terms\nof
an automaton group\, and\, until Nekrashevych's very recent work\, all\nt
he known examples of intermediate growth groups were automaton groups\nor
based on automaton groups.\n\nThis talk originates in the following questi
on: is it decidable if an\nautomaton group has intermediate growth? I will
show that in the\ncase of bireversible automata\, whenever there exists a
t least one\nelement of infinite order\, the growth of the group is necess
arily\nexponential.\n\n(This work will be presented at ICALP'18.)
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Simple and Optimal Complementation Algorithm for Büchi-Automata
- Ulrich Ultes-Nitsche\, University of Fribourg
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180525T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180525T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:602
DESCRIPTION:In my presentation\, I am going to present joint work with Joe
l Allred on the complementation of Büchi automata. When constructing the
complement automaton\, a worst-case state-space growth of O((0.76n)^n) can
not be avoided. Experiments suggest that complementation algorithms perfor
m better on average when they are structurally simple. We develop a simple
algorithm for complementing Büchi automata\, operating directly on subse
ts of states\, structured into state-set tuples\, and producing a determin
istic automaton. Then a complementation procedure is applied that resemble
s the straightforward complementation algorithm for deterministic Büchi a
utomata\, the latter algorithm actually being a special case of our constr
uction. Finally\, we prove our construction to be optimal\, i.e. having an
upper bound in O((0.76n)^n)\, and furthermore calculate the 0.76 factor i
n a novel exact way.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:The complexity of carry propagation for successor functions - Jacq
ues Sakarovitch\, IRIF/CNRS and Telecom ParisTech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180629T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180629T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:615
DESCRIPTION:Given any numeration system\, we call 'carry propagation' at a
\nnumber N the number of digits that are changed when going from the\nrepr
esentation of N to the one of N+1 \, and 'amortized carry\npropagation' t
he limit of the mean of the carry propagations at the\nfirst N integers\,
when N tends to infinity\, and if it exists.\n\nWe address the problem of
the existence of the amortized carry\npropagation and of its value in non
-standard numeration systems of\nvarious kinds: abstract numeration system
s\, rational base numeration\nsystems\, greedy numeration systems and beta
-numeration.\n\nWe tackle the problem by means of techniques of three diff
erent types:\ncombinatorial\, algebraic\, and ergodic.\n\nFor each kind of
numeration systems that we consider\, the relevant\nmethod allows to esta
blish sufficient conditions for the existence of\nthe carry propagation an
d examples show that these conditions are\nclose to be necessary.\n\nThis
is a joint work with Valérie Berthé\, Christiane Frougny\, and Michel Ri
go
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Where the universal trees grow - Nathanaël Fijalkow\, LABRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180622T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180622T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:616
DESCRIPTION:I will talk about parity games. There are at least three diffe
rent recent algorithms which solve them in quasipolynomial time. In this t
alk\, I will show that the three algorithms can be seen as solutions of on
e automata-theoretic problem. Using this framework\, I will show tight upp
er and lower bounds\, witnessing a quasipolynomial barrier.\n\nThis is bas
ed on two joint works\, the first with Wojtek Czerwinski\, Laure Daviaud\,
Marcin Jurdzinski\, Ranko Lazic\, and Pawel Parys\,\nand the second with
Thomas Colcombet.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Program Invariants - Joël Ouaknine\, Max Planck Institute
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180613T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180613T160000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:617
DESCRIPTION:Automated invariant generation is a fundamental challenge in p
rogram analysis and verification\, going back many decades\, and remains a
topic of active research. In this talk I'll present a select overview and
survey of work on this problem\, and discuss unexpected connections to ot
her fields including algebraic geometry\, group theory\, and quantum compu
ting. (No previous knowledge of these fields will be assumed.)\n\nThis is
joint work with Ehud Hrushovski\, Amaury Pouly\, and James Worrell.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Unifying non-commutative arithmetic circuit lower bounds - Pierre
Ohlmann\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180615T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180615T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:624
DESCRIPTION:We develop an algebraic lower bound technique in the context \
nof non-commutative arithmetic circuits. To this end\, we introduce \npoly
nomials for which the multiplication is also non-associative\, and\nfocus
on their circuit complexity. We show a connection with \nmultiplicity tree
automata\, leading to a general algebraic \ncharacterization. We use it t
o derive meta-theorems for the \nnon-commutative case\, and highlight nume
rous consequences in terms of \nlower bounds.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:tba - Sam Van Gool\, University of Amsterdam\, ILLC
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181005T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181005T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:629
DESCRIPTION:tba
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Counter Machines and Distributed Automata: A Story about Exchangin
g Space and Time - Fabian Reiter\, LSV
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181109T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181109T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:665
DESCRIPTION:I will present the equivalence of two classes of counter machi
nes\nand one class of distributed automata. The considered counter\nmachin
es operate on finite words\, which they read from left to\nright while inc
rementing or decrementing a fixed number of\ncounters. The two classes dif
fer in the extra features they\noffer: one allows to copy counter values\,
whereas the other\nallows to compute copyless sums of counters. The consi
dered\ndistributed automata\, on the other hand\, operate on directed path
\ngraphs that represent words. All nodes of a path synchronously\nexecute
the same finite-state machine\, whose state diagram must\nbe acyclic excep
t for self-loops\, and each node receives as input\nthe state of its direc
t predecessor. These devices form a\nsubclass of linear-time one-way cellu
lar automata.\n\nThis is joint work with Olivier Carton and Bruno Guillon.
LOCATION:Salle 358
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finding short synchronizing and mortal words for prefix codes - An
drew Rizhikov\, University Paris-Est Marne-la-Vallée
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181019T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181019T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:675
DESCRIPTION:We study approximation algorithms for two closely related prob
lems: the problems of finding a short synchronizing and a short mortal wor
d for a given prefix code. Roughly speaking\, a synchronizing word is a wo
rd guaranteeing a unique interpretation\, and a mortal word is a word guar
anteeing no interpretation for any sequence of codewords. We concentrate o
n the case of finite prefix codes and consider both the cases where the co
de is defined by listing all its codewords and where the code is defined b
y an automaton recognizing the star of the code. This is a joint work with
Marek Szykuła (University of Wroclaw).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Groups\, languages and dendric shifts - Dominique Perrin\, Univers
ité Paris-Est Marne-la-Vallée
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181130T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181130T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:676
DESCRIPTION:We present a survey of results obtained on symbolic dynamical\
nsystems called dendric shifts. We state and sketch the\nproofs (sometimes
new ones) of the main results\nobtained on these shifts. This includes th
e Return\nTheorem and the Finite Index Basis Theorem which both\nput in ev
idence the central role played by free groups in these\nsystems. We also p
resent a series of applications of these results\,\nincluding some on prof
inite semigroups and some on dimension\ngroups.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Topological Sorting under Regular Constraints - Antoine Amarilli\,
Télécom ParisTech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181207T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181207T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:678
DESCRIPTION:We present our work on what we call the constrained topologica
l sorting problem (CTS): given a regular language K and a directed acyclic
graph G with labeled vertices\, determine if G has a topological sort tha
t forms a word in K. This natural problem applies to several settings\, e.
g.\, scheduling with costs or verifying concurrent programs. We consider t
he problem CTS[K] where the target language K is fixed\, and study its com
plexity depending on K.\n\nOur work shows that CTS[K] is tractable when K
falls in several language families\, e.g.\,\nunions of monomials\, which c
an be used for pattern matching. However\, we can show that CTS[K] is NP-h
ard for K = (ab)^* using a shuffle reduction technique that we can use to
show hardness for more languages. We also study the special case of the co
nstrained shuffle problem (CSh)\, where the input graph is a disjoint unio
n of strings\, and show that CSh[K] is additionally tractable when K is a
group language or a union of district group monomials. We conjecture that
a dichotomy should hold on the complexity of CTS[K] or CSh[K] depending on
K\, and substantiate this by proving a coarser dichotomy under a differen
t problem phrasing which ensures that tractable languages are closed under
common operators.
LOCATION:Salle 3058
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Curry-Howard approach to tree automata - Colin Riba\, École Nor
male Supérieure de Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181214T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181214T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:679
DESCRIPTION:Rabin's Tree Theorem proceeds by effective translations of MSO
-formulae to tree automata. We show that the operations on automata used i
n these translations can be organized in a deduction system based on intui
tionistic linear logic (ILL). We propose a computational interpretation of
this deduction system along the lines of the Curry-Howard proofs-as-progr
ams correspondence. This interpretation\, relying on the usual technology
of game semantics\, maps proofs to strategies in categories of two-player
games generalizing the usual acceptance games of tree automata.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Reachability Problem for Petri Nets is Not Elementary - Jérô
me Leroux\, LaBRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181221T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181221T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:695
DESCRIPTION:Petri nets\, also known as vector addition systems\, are a lon
g established and widely used model of concurrent processes. The complexit
y of their reachability problem is one of the most prominent open question
s in the theory of verification. That the reachability problem is decidabl
e was established by Mayr in his seminal STOC 1981 work\, and the currentl
y best upper bound is non-primitive recursive cubic-Ackermannian of Leroux
and Schmitz from LICS 2015. We show that the reachability problem is not
elementary. Until this work\, the best lower bound has been exponential sp
ace\, due to Lipton in 1976.\n\nJoint work with Wojciech Czerwinski\, Slaw
omir Lasota\, Ranko Lazic\, Filip Mazowiecki.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:A way to extend the Pascal triangle to words - Manon Stipulanti\,
Université de Liège
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181116T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181116T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:696
DESCRIPTION:The Pascal triangle and the corresponding Sierpinski gasket ar
e well-studied objects. They exhibit self-similarity features and have con
nections with dynamical systems\, cellular automata\, number theory and au
tomatic sequences in combinatorics on words. In this talk\, I will first r
ecall the well-known link between those two objects. Then I will exploit i
t to define Pascal-like triangles associated with different numeration sys
tems\, and their analogues of the Sierpinski gasket. \nThis a work in coll
aboration with Julien Leroy and Michel Rigo (University of Liège\, Belgiu
m).
LOCATION:Salle 358
END:VEVENT
BEGIN:VEVENT
SUMMARY:Structure substitutive des pavages apériodiques de Jeandel-Rao -
Sébastien Labbé\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181123T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181123T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:705
DESCRIPTION:En 2015\, Jeandel et Rao ont démontré par des calculs exhaus
tifs faits par ordinateur que tout ensemble de tuiles de Wang de cardinali
té ≤ 10 soit admettent un pavage périodique du plan Z² soit n'admette
nt aucun pavage du plan. De plus\, ils ont trouvé un ensemble de 11 tuile
s de Wang qui pavent le plan mais jamais de façon périodique. Dans cet e
xposé\, nous présenterons une définition alternative des pavages apéri
odiques de Jeandel-Rao comme le codage d'une Z²-action sur le tore et nou
s décrivons la structure substitutive de ces pavages.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Discrepancy and nested perfect necklaces - Olivier Carton\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190111T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190111T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:733
DESCRIPTION:M. B. Levin constructed a real number x such that the first N
terms of the\nsequence b^n x mod 1 for n >= 1 have discrepancy $O((log N)^
2/N)$. This is\nthe lowest discrepancy known for this kind of sequences.
In this talk\, we\npresent Levin's construction in terms of nested perfec
t necklaces\, which\nare a variant of the classical de Bruijn sequences.
For base 2 and the\norder being a power of 2\, we give the exact number of
nested perfect\nnecklaces and an explicit method based on matrices to con
struct each of\nthem.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Learning Top-Down Tree Transducers using Myhill Nerode or Lookahea
d - Adrien Boiret
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190118T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190118T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:734
DESCRIPTION:We consider the problem of passive symbolic learning in the ca
se of deterministic top-down tree transducers (DTOP).\nThe passive learnin
g problem deals with identifying a specific transducer in normal form from
a finite set of behaviour examples.\nThis problem is solved in word langu
ages using the RPNI algorithm\, that relies heavily on the Myhill-Nerode c
haracterization of a minimal normal form on DFA. Its extensions to word tr
ansformations and tree languages follow the same pattern: first\, a Myhill
-Nerode theorem is identified\, then the normal form it induces can be lea
rnt from examples.\nTo adapt this result in tree transducers\, the Myhill-
Nerode theorem requires that DTOP are considered with an inspection\, i.e.
an automaton that recognized the domain of the transformation. In its ori
ginal form\, the normalization (minimal earliest compatible normal form) a
nd learning of DTOP is limited to deterministic top-down tree automata as
inspections.\nIn this talk\, we show the challenges that an extension to r
egular inspections presents\, and present two concurrent ways to deal with
them:\n - first\, by an extension of the Myhill-Nerode theorem on DTOP
to the regular case\, by defining a minimal *leftmost* earliest compatibl
e normal form.\n - second\, by reducing the problem to top-down domains
\, by using the regular inspection as a lookahead\nThe merits of these met
hods will be discussed for possible extensions of these methods to data tr
ees.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:The power of programs over monoids taken from some small varieties
of finite monoids - Nathan Grosshans
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190125T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190125T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:735
DESCRIPTION:The computational model of programs over monoids\, introduced
by Barrington and Thérien in the late 1980s\, gives a way to generalise t
he notion of (classical) recognition through morphisms into monoids in suc
h a way that almost all open questions about the internal structure of the
complexity class NC^1 can be reformulated as understanding what languages
(and\, in fact\, even regular languages) can be program-recognised by mon
oids taken from some given variety of finite monoids. Unfortunately\, for
the moment\, this finite semigroup theoretical approach did not help to pr
ove any new result about the internal structure of NC^1 and\, even worse\,
any attempt to reprove well-known results about this internal structure (
like the fact that the language of words over the binary alphabet containi
ng a number of 1s not divisible by some fixed integer greater than 1 is no
t in AC^0) using techniques stemming from algebraic automata theory failed
.\nIn this talk\, I shall present the model of programs over monoids\, exp
lain how it relates to "small" circuit complexity classes and present some
of the contributions I made during my Ph.D. thesis to the understanding o
f the computational power of programs over monoids\, focusing on the well-
known varieties of finite monoids DA and J (giving rise to "small" circuit
complexity classes well within AC^0). I shall conclude with a word about
ongoing work and future research directions.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Query enumeration and nowhere dense classes of graphs - Alexandre
Vigny\, Université Paris Diderot
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190215T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190215T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:746
DESCRIPTION:Given a query q and a relational structure D the enumeration o
f q over D consists in computing\, one element at a time\, the set q(D) of
all solutions to q on D. The delay is the maximal time between two consec
utive output and the preprocessing time is the time needed to produce the
first solution. Ideally\, we would like to have constant delay enumeration
after linear preprocessing. Since this it is not always possible to achie
ve\, we need to add restrictions to the classes of structures and/or queri
es we consider.\n\nIn this talk I will talk about some restrictions for wh
ich such algorithms exist: graphs with bounded degree\, tree-like structur
es\, conjunctive queries...\nWe will more specifically consider nowhere de
nse classes of graphs: What are they? Why is this notion relevant? How to
make algorithms from these graph properties?
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:New notions of recurrence in a multidimensional setting - Elise Va
ndomme\, Université Technique Tchèque de Prague
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190201T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190201T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:752
DESCRIPTION:In one dimension\, an infinite word is said to be recurrent if
every prefix occurs at least twice. A straightforward extension of this d
efinition in higher dimensions turns out to be rather unsatisfying. In thi
s talk\, we present several notions of recurrence in the multidimensional
case. In particular\, we are interested in words having the property to be
strongly uniformly recurrent: for each direction q\, every prefix occurs
in that direction (i.e. in positions iq) with bounded gaps. We will provid
e several constructions of such words and focus on the strongly uniform re
currence in the case of square morphisms.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Versions quantitatives du théorème de Christol - Reem Yassawi\,
CNRS\, Institut Camille Jordan - Université Lyon 1 - Claude Bernard
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190322T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190322T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:763
DESCRIPTION:Pour une suite $\\mathbb{a} = (a_n)_{n≥0}$ à valeurs dans u
n corps fini $\\mathbb{F}_q$\, le théorème de Christol établit une équ
ivalence entre $q$-automaticité de $\\mathbb{a}$ ($\\mathbb{a}$ calculabl
e par un automate) et l’algebricité de la série formelle $f(x) = \\sum
a_n x^n$. Dans ce travail nous étudierons le nombre d’états de l’a
utomate en fonction des paramètres du polynôme annulateur minimal de $f(
x)$.\n\nAndrew Bridy a récemment donne une démonstration du théorème d
e Christol en utilisant des outils qui proviennent de la géométrie algé
brique. Avec cette démonstration il majore le nombre d’états par une b
orne qui est optimale. Nous obtenons des bornes presque semblables par une
démonstration élémentaire\, et nous traçons les liens entre notre dé
monstration et celle de Bridy. Ceci est un travail en commun avec Boris Ad
amczewski.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Higher-order parity automata - Paul-André Melliès\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190208T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190208T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:782
DESCRIPTION:In this talk\, I will introduce a notion of higher-order parit
y automaton which extends the traditional notion of parity tree automaton
on infinitary ranked trees to the infinitary simply-typed lambda-calculus.
Our main result is that the acceptance of an infinitary lambda-term by a
higher-order parity automaton A is decidable\, whenever the infinitary lam
bda-term is generated by a finite and simply-typed lambda-Y-term. The deci
dability theorem is established by combining ideas coming from automata th
eory\, denotational semantics and infinitary rewriting theory. \n\nYou wil
l find the extended abstract of the talk here:\nhttps://www.irif.fr/~melli
es/papers/higher-order-parity-automata.pdf
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Points apériodiques dans la sous shifts de dimension 2 - Anaël G
randjean
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190329T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190329T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:801
DESCRIPTION:La théorie des espaces de pavages (sous-shifts) a été profo
ndément façonnée par le résultat historique de Berger : un jeu de tuil
es fini peut ne paver le plan que de manière apériodique. Ces points ap
ériodiques sont au coeur de nombreuses directions de recherche du domaine
\, en mathématiques comme en informatique. Dans cette exposé\, nous rép
ondons aux questions suivantes en dimension 2 :\n\nQuelle est la complexit
é calculatoire de déterminer si un jeu de tuiles (espace de type fini) p
ossède un point apériodique ? Comment se comportent les espaces de pavag
es ne possédant aucun point apériodique ?\n\nNous montrons qu’un espac
e de pavage 2D sans point apériodique a une structure très forte : il es
t “équivalent” (presque conjugué) à un espace de pavage 1D\, et ce
résultat s’applique aux espaces de type fini ou non. Nous en déduisons
que le problème de posséder un point apériodique est co-récursivement
-énumérable-complet\, et que la plupart des propriétés et méthodes pr
opres au cas 1D s’appliquent aux espaces 2D sans point apériodique. La
situation en dimension supérieure semble beaucoup moins claire.\n\nCet ex
posé est issu d’une collaboration avec Benjamin Hellouin de Menibus et
Pascal Vanier.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Condition numbers of stochastic mean payoff games and what they sa
y about nonarchimedean convex optimization - Mateusz Skomra\, ÉNS Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190315T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190315T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:802
DESCRIPTION:In this talk\, we introduce a condition number of stochastic m
ean payoff games. To do so\, we interpret these games as feasibility probl
ems over tropically convex cones. In this setting\, the condition number i
s defined as the maximal radius of a ball in Hilbert's projective metric t
hat is included in the (primal or dual) feasible set. We show that this c
onditioning controls the number of value iterations needed to decide wheth
er a mean payoff game is winning. In particular\, we obtain a pseudopolyno
mial bound for the complexity of value iteration provided that the number
of random positions is fixed. We also discuss the implications of these re
sults for convex optimization problems over nonarchimedean fields and pres
ent possible directions for future research.\n\nThe talk is based on joint
works with X. Allamigeon\, S. Gaubert\, and R. D. Katz.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christoffel words and applications. - Lama Tarsissi\, Université
Marne-la-Vallée\, Paris Est
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190308T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190308T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:826
DESCRIPTION:It is known that Christoffel words are balanced words on two l
etters alphabet\, where these words are\nexactly the discretization of lin
e segments of rational slope. Christoffel words are\nconsidered also in th
e topic of synchronization of k process by a word on a k letter\nalphabet
with a balance property in each letter. Some applications for k = 2\, we r
etrieve the usual Christoffel words. While for k > 2\, the situation is mo
re complicated and lead to the Fraenkel’s conjecture that is an open con
jecture for more than 40 years. In this talk\, we show some tools that get
us close to this conjecture. Another application to this family of words\
, we define a second order of balance by using some particular matrices\,
and we prove a recursive relation in constructing them. An interesting pro
perty can be deduced from these matrices\, allowing us to give a supplemen
tary characteristic for the Fibonnaci sequence. One more application to C
hristoffel words is discussed in this talk\, in fact\, by using all the pr
operties of these words\, we can apply them on the reconstruction of digi
tal convex polyominoes. Since the boundary word of the digital convex poly
ominoe is made of Christoffel words with decreasing slopes. Hence we intro
duce a split operator that respects the decreasing order of the slopes and
therefore the convexity is always conserved which is the first step towar
d this reconstruction.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Separation and covering for varieties determined by groups - Sam V
an Gool\, Utrecht University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190503T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190503T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:830
DESCRIPTION:The separation problem for a variety of regular languages V as
ks to decide whether two disjoint regular languages can be separated by a
language in V. The covering problem is a generalization of the separation
problem to an arbitrary finite list of regular languages. \n\nThe covering
problem for the variety of star-free languages was shown to be decidable
by Henckell. In fact\, he gave an algorithm for an equivalent problem\, na
mely\, computing the pointlike subsets of a finite semigroup with respect
to the variety of aperiodic semigroups\, i.e.\, semigroups all of whose su
bgroups are trivial. \n\nIn this talk\, I will present the following wide
generalization of Henckell's result. Let H be any decidable variety of gro
ups. I will describe an algorithm for computing pointlike sets for the var
iety of semigroups all of whose subgroups are in H. The correctness proof
for the algorithm uses asynchronous transducers\, Schützenberger groups\,
and self-similarity. An application of our result is the decidability of
the covering and separation problems for the variety of languages definab
le in first order logic with modular counting quantifiers.\n\nThis talk is
based on our paper S. v. Gool & B. Steinberg\, Adv. in Math. 348\, 18-50
(2019).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Generalized Lyndon words - Francesco Dolce\, Université Paris Did
erot\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190326T130000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190326T140000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:844
DESCRIPTION:A generalized lexicographical order on infinite words is defin
ed by choosing for each position a total order on the alphabet. This allow
s to define generalized Lyndon words. Every word in the free monoid can be
factorized in a unique way as a non-increasing factorization of generaliz
ed Lyndon words. We give new characterizations of the first and the last f
actor in this factorization as well as new characterization of generalized
Lyndon words. We also give more specific results on two special cases: th
e classical one and the one arising from the alternating lexicographical o
rder. This is a joint work with Antonio Restivo and Christophe Reutenauer.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Probabilistic Timed Automata with Clock-Dependent Probabilities -
Jeremy Sproston\, Université de Turin
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190517T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190517T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:882
DESCRIPTION:Probabilistic timed automata are classical timed automata exte
nded with discrete probability distributions over edges. In this talk\, cl
ock-dependent probabilistic timed automata\, a variant of probabilistic ti
med automata in which transition probabilities can depend on clock values\
, will be described. Clock-dependent probabilistic timed automata allow th
e modelling of a continuous relationship between time passage and the like
lihood of system events. We show that the problem of deciding whether the
maximum probability of reaching a certain location is above a threshold is
undecidable for clock-dependent probabilistic timed automata. On the othe
r hand\, we show that the maximum and minimum probability of reaching a
certain location in clock-dependent probabilistic timed automata can be ap
proximated using a region-graph-based approach.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Un théorème de Mahler pour les fonctions de mots. (Jean-Eric Pin
et Christophe Reutenauer) - Jean-Éric Pin\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190607T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190607T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:889
DESCRIPTION:Soit $p$ un nombre premier et soit $G_p$ la variété de tous
les langages reconnus par un $p$-groupe fini (i.e. un groupe d'ordre une p
uissance de $p$). \nOn donne deux façons de construire toutes les fonctio
ns $f$ de $A^*$ dans $B^*$ (et même dans $F(B)$\, le groupe libre de base
$B$) qui possèdent la propriété suivante: si $L$ est une partie de $F(
B)$ reconnue par un $p$-groupe fini\, alors $f^{-1}(L)$ a la même propri
été. Ce résultat découle d'une version non-commutative des séries de
Newton et d'un célèbre théorème de Mahler en analyse $p$-adique.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Büchi Objectives in Countable MDPs - Mahsa Shirmohammadi\, CNRS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190705T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190705T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:897
DESCRIPTION:We study countably infinite Markov decision processes with Bü
chi objectives\, which ask to visit a given subset of states infinitely of
ten. A question left open by T.P. Hill in 1979 is whether there always exi
st ε-optimal Markov strategies\, i.e.\, strategies that base decisions on
ly on the current state and the number of steps taken so far. We provide a
negative answer to this question by constructing a non-trivial counterexa
mple. On the other hand\, we show that Markov strategies with only 1 bit o
f extra memory are sufficient.\nThis work is in collaboration with Stefan
Kiefer\, Richard Mayr and Patrick Totzke\, and is going to be presented in
ICALP 2019. A full version is at https://arxiv.org/abs/1904.11573
LOCATION:Salle 1001
END:VEVENT
BEGIN:VEVENT
SUMMARY:Simple Priced Timed Games are not That Simple - Engel Lefaucheux\,
Max-Planck Institute for Software Systems\, Saarbrucken
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190614T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190614T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:901
DESCRIPTION:Priced timed games are two-player zero-sum games played on pri
ced\ntimed automata (whose locations and transitions are labeled by\nweigh
ts modeling the price of spending time in a state and executing\nan action
\, respectively). The goals of the players are to minimise\nor maximise th
e price to reach a target location.\nWhile one can compute the optimal val
ues that the players can achieve\n(and their associated optimal strategies
) when the weights are all\npositive\, this problem with arbitrary integer
weights remains open.\nIn this talk\, I will explain what makes this case
more difficult and\nshow how to solve the problem for a subclass of price
d timed\ngames (the so-called simple priced timed games).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pebble transducers for modeling simple programs - Gaëtan Douénea
u-Tabot\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191011T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191011T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:931
DESCRIPTION:Several models of automata with outputs (known as transducers)
have \nbeen defined over the years to describe various classes of \n"re
gular-like" functions. Such classes generally have good \ndecidability pr
operties\, and they have been shown especially relevant \nfor program ver
ification or synthesis. In this talk\, we shall \ninvestigate pebble tran
sducers\, i.e. finite-state machines that can \ndrop nested marks on thei
r input. We provide various correspondences \nbetween these models and tr
ansducers that use registers\, and we solve \nrelated membership problems
. These results can be understood as \ntechniques for program optimizatio
n\, that can be useful in practice. \nThis talk is based on joint work wi
th P. Gastin and E. Filiot.
LOCATION:Salle 1016
END:VEVENT
BEGIN:VEVENT
SUMMARY:Deciding language inclusion problems using quasiorders - Pierre Ga
nty\, IMDEA Software Institute
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191028T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191028T120000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:942
DESCRIPTION:We study the language inclusion problem L1 ⊆ L2 where L1 is
regular or \ncontext-free. Our approach checks whether an overapproximatio
n of L1 is \nincluded in L2. Such overapproximations are obtained using qu
asiorder \nrelations on words where the abstraction gives the language of
all words \n“greater than or equal to” a given input word for that qua
siorder. We \nput forward a range of quasiorders that allow us to systemat
ically \ndesign decision procedures for different language inclusion probl
ems \nsuch as context-free languages into regular languages and regular \n
languages into trace sets of one-counter nets.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Timed Basic Parallel Processes - Patrick Totzke
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191115T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191115T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:943
DESCRIPTION:I will talk about two fun constructions for reachability analy
sis of \none-clock\ntimed automata\, which lead to concise logical charact
erizations in \nexistential\nLinear Arithmetic.\n\nThe first one describes
"punctual" reachability relations: reachability \nin\nexact time t. It us
es a coarse interval abstraction and counting of \nresets via\nParikh-Auto
mata.\nThe other is a "sweep line" construction to compute optimal time to
\nreach in\nreachability games played on one-clock TA.\n\nTogether\, thes
e can be used to derive a (tight) NP complexity upper \nbound for\nthe cov
erability and reachability problems in an interesting subclass of \nTimed\
nPetri Nets\, which naturally lends itself to parametrised safety checking
\nof\nconcurrent\, real-time systems. This contrasts with known \nsuper-A
ckermannian\ncompleteness\, and undecidability results for unrestricted Ti
med Petri \nnets.\n\nThis is joint work with Lorenzo Clemente and Piotr Ho
fman\, and was \npresented at\nCONCUR'19. Full details are available at \n
https://arxiv.org/abs/1907.01240.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noncommutative rational Pólya series - Daniel Smertnig\, Universi
ty of Waterloo
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191108T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191108T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:944
DESCRIPTION:A rational series is a noncommutative formal power series whos
e \ncoefficients are recognized by a weighted finite automaton (WFA). A \n
rational series with coefficients in a field $K$ is a Pólya series if \na
ll nonzero coefficients are contained in a finitely generated subgroup \no
f $K^\\times$. Generalizing results of Pólya (1921)\, Benzaghou (1970)\,
\nand Bézivin (1987) for the univariate case\, we show that Pólya series
\nare precisely the ones recognized by unambiguous WFAs.\n\nThis is joint
work with Jason Bell. arXiv:1906.07271
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Limits of finite structures: a duality theoretic perspective - Luc
a Reggio\, Mathematical Institute\, University of Bern
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191025T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191025T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:947
DESCRIPTION:A systematic approach to the study of limits of finite structu
res\, motivated by investigations in graph theory\, has been developed by
Nešetřil and Ossona de Mendez starting in 2012. The basic idea consists
in embedding the set of finite structures into a space of measures which i
s complete\, so that every converging sequence of finite structures admits
a limit. This limit point can be always realized as a measure.\n\nI will
explain how this embedding into a space of measures dually corresponds to
enriching First-Order Logic with certain probability operators. Further\,
I will relate this construction to first-order quantification in logic on
words.\n\nThis talk is based on joint work with M. Gehrke and T. Jakl.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the complexity of linear arithmetic theories over the integers
- Dmitry Chistikov\, University of Warwick
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191129T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191129T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:948
DESCRIPTION:Given a system of linear Diophantine equations\, how difficult
is it to\ndetermine whether it has a solution? What changes if equations
are replaced\nwith inequalities? If some of the variables are quantified u
niversally?\nThese and similar questions relate to the computational compl
exity of deciding\nthe truth value of statements in various logics. This i
ncludes in particular\nPresburger arithmetic\, the first-order logic over
the integers with addition\nand order.\n\nIn this talk\, I will survey con
structions and ideas that underlie known\nanswers to these questions\, fro
m classical results to recent developments\,\nand open problems.\n\nFirst\
, we will recall the geometry of integer linear programming and how it\nin
teracts with quantifiers. This will take us from classical results\ndue to
von zur Gathen and Sieveking (1978)\, Papadimitriou (1981)\, and others\n
to the geometry of the set of models of quantified logical formulas. We wi
ll\nlook at rational convex polyhedra and their discrete analogue\, hybrid
linear\nsets (joint work with Haase (2017))\, and see\, in particular\, h
ow the latter\nform a proper sub-family of ultimately periodic sets of int
eger points in\nseveral dimensions (the semi-linear sets\, introduced by P
arikh (1961)).\n\nSecond\, we will discuss "sources of hardness": which as
pects of the expressive\npower make decision problems for logics over the
integers hard. Addition and\nmultiplication combined enable simulation of
arbitrary Turing machines\, and\nrestriction of multiplication to bounded
integers corresponds to\nresource-bounded Turing machines. How big can the
se bounded integers be in\nPresburger arithmetic? This leads to the proble
m of representing big numbers\nwith small logical formulae\, and we will s
ee constructions by Fischer and\nRabin (1974) and by Haase (2014). We will
also look at the new "route" for\nexpressing arithmetic progressions (in
the presence of quantifier alternation)\nvia continued fractions\, recentl
y discovered by Nguyen and Pak (2017).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Décider (R\,+\,<\,1) dans (R\,+\,<\,Z) - Alexis Bes
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191122T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191122T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:955
DESCRIPTION:La structure (R\,+\,<\,Z)\, où R désigne l'ensemble des rée
ls et Z le \nprédicat unaire "être un entier"\, admet l'élimination des
\nquantificateurs et est décidable. Elle intervient notamment dans le \nd
omaine de la spécification et la vérification de systèmes hybrides. \nE
lle peut être étudiée via les automates\, en considérant des automates
\nde Büchi qui lisent des réels représentés dans une base entière fi
xée. \nBoigelot et al. ont démontré en particulier que la classe des re
lations \ndéfinissables dans (R\,+\,<\,Z) coïncide avec celle des relati
ons \nreconnaissables par automate en toute base. Une autre structure \nin
téressante est (R\,+\,<\,1)\, qui est moins expressive que (R\,+\,<\,Z) m
ais \ndéfinit les mêmes relations bornées. On présente une caractéris
ation \ntopologique des relations définissables dans (R\,+\,<\,Z) qui son
t \ndéfinissables dans (R\,+\,<\,1)\, et on en déduit que le problème d
e savoir \nsi une relation définissable dans (R\,+\,<\,Z) est définissab
le dans \n(R\,+\,<\,1) est décidable.\nTravail en commun avec Christian C
hoffrut.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Residuation: Origins and Open Problems - Wesley Fussner
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191206T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191206T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:977
DESCRIPTION:Residuated lattices are a variety of ordered monoids whose stu
dy arises \nfrom from three directions: Algebras of ideals of rings\, alge
bras of \nbinary relations\, and the semantics of substructural logics. Th
is talk \nprovides a survey of residuated lattices\, discussing both their
\nhistorical origins and current threads of research. We also offer an \n
introduction to some difficult problems that arise their study\, in \npart
icular connected to structure theorems for special classes of \nresiduated
lattices and their duality theory.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Marc Zeitoun
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200117T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200117T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:1009
DESCRIPTION:TBA
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Karoliina Lehtinen
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200110T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200110T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:1010
DESCRIPTION:TBA
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Trade-offs Between Size and Degree in Polynomial Calculus - Guilla
ume Lagarde\, LABRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191213T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191213T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:1023
DESCRIPTION:Introduced by Cleggs et al. (STOC'96) to capture Gröbner basi
s computations\, Polynomial Calculus Resolution (PCR) is an algebraic proo
f system for certifying the unsatisfiability of CNF formulas. Impagliazzo
et al. (CC'99) established that if an unsatisfiable k-CNF formula over n v
ariables has a PCR refutation of small size (that is\, polynomial size)\,
then this formula also has a refutation of small degree\, i.e.\, O(sqrt(n
log n)). A natural question is to know whether we can achieve both small s
ize and small degree in the same refutation. A situation similar in spirit
arises in the more classical resolution proof system where degree is repl
aced by width and size by length. In this setting\, Thapen (TOC '16) adres
sed the tradeoff question by providing a negative answer: the decrease in
width necessarily comes at the expense of an exponential blow-up in length
. Extending ideas from Thapen\, our main result is to prove that a strong
size-degree tradeoff is also necessary in PCR.\n\nJoint work with Jakob No
rdström\, Dmitry Sokolov\, Joseph Swernofsky
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Achim Blumensath\, Masaryk University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191217T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191217T153000
DTSTAMP;VALUE=DATE-TIME:20191207T110300Z
UID:1026
DESCRIPTION:TBA
LOCATION:Salle 0010
END:VEVENT
END:VCALENDAR