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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:20220119T070300Z
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:The star-free closure - Marc Zeitoun\, LABRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200117T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200117T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1009
DESCRIPTION:A language of finite words is star-free when it can be built f
rom letters using Boolean operations and concatenation. A well-known theor
em of Schützenberger characterizes star-free languages as those recognize
d by an aperiodic monoid. Another theorem of Schützenberger gives an alte
rnate definition: these are the languages that can be built using product\
, union\, and\, in a limited way\, Kleene star (but complement is now disa
llowed). \n\nThese definitions can be rephrased using closure operators op
erating on classes of languages. In this talk\, we investigate these opera
tors and generalize the results of Schützenberger. This is joint work wit
h Thomas Place.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Parity Games -- the quasi-polynomial era - Karoliina Lehtinen
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200110T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200110T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1010
DESCRIPTION:Parity games are central to the verification and synthesis of
reactive systems: various model-checking\, realisability and synthesis pro
blems reduce to solving these games. Solving parity games -- that is\, dec
iding which player has a\nwinning strategy -- is one of the few problems k
nown to be in both UP and co-UP yet not known to be in P. So far\, the que
st for a polynomial algorithm has lasted over 25 years.\n\nIn 2017 a major
breakthrough occurred: parity games are solvable in quasi-polynomial time
.\nSince then\, several seemingly very distinct quasi-polynomial algorithm
s have been published\, both by myself and others\, and some of the novel
ideas behind them have been applied to address other problems in automata
theory.\n\nIn this talk\, I will give an overview of these developments\,
including my own contribution to them\, and the state-of-the art\, with a
slight automata-theoretic bias.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Regular Tree Algebras - Achim Blumensath\, Masaryk University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191217T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191217T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1026
DESCRIPTION:I present recent developments concerning a very general algebr
aic\n theory for languages of infinite trees which is based on the\n categ
ory-theoretical notion of a monad. The main result isolates a\n class of a
lgebras that precisely captures the notion of regularity for\n such langua
ges. In particular\, we show that these algebras form a\n pseudo-variety a
nd that syntactic algebras exists. If time permits I\n will conclude the t
alk with a few simple characterisation results\n obtained using this frame
work.
LOCATION:Salle 0010
END:VEVENT
BEGIN:VEVENT
SUMMARY:Deciding the existence of cut-off in parameterized rendez-vous net
works - Arnaud Sangnier\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200131T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200131T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1053
DESCRIPTION:We study networks of processes which all execute the same\nfi
nite-state protocol and communicate thanks to a rendez-vous\nmechanism. Gi
ven a protocol\, we are interested in checking whether\nthere exists a num
ber\, called a cut-off\, such that in any networks with a bigger\nnumber o
f participants\, there is an execution where all the\nentities end in some
final states. We provide decidability and\ncomplexity results of this pro
blem under various assumptions\, such as\nabsence/presence of a leader or
symmetric/asymmetric rendez-vous.\n\nThis is a joint work with Florian Hor
n.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Life is random time is not: Markov decision processes with window
objectives - Youssouf Oualhadj\, LACL
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200207T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200207T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1054
DESCRIPTION:The window mechanism was introduced by Chatterjee et al. to st
rengthen classical game objectives with time bounds. It permits to synthes
ize system controllers that exhibit acceptable behaviors within a configur
able time frame\, all along their infinite execution\, in contrast to the
traditional objectives that only require correctness of behaviors in the l
imit. The window concept has proved its interest in a variety of two-playe
r zero-sum games\, thanks to the ability to reason about such time bounds
in system specifications\, but also the increased tractability that it usu
ally yields.\n\nIn this work\, we extend the window framework to stochasti
c environments by considering the fundamental threshold probability proble
m in Markov decision processes for window objectives. That is\, given such
an objective\, we want to synthesize strategies that guarantee satisfying
runs with a given probability. We solve this problem for the usual varian
ts of window objectives\, where either the time frame is set as a paramete
r\, or we ask if such a time frame exists. We develop a generic approach f
or window-based objectives and instantiate it for the classical mean-payof
f and parity objectives\, already considered in games. Our work paves the
way to a wide use of the window mechanism in stochastic models.\n\nJoint w
ork with : Thomas Brihaye\, Florent Delgrange\, Mickael Randour.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weight Annotation in Information Extraction - Liat Peterfreund\, I
RIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200529T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200529T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1061
DESCRIPTION:The framework of document spanners abstracts the task of infor
mation extraction from text as a function that maps every document (a stri
ng) into a relation over the document’s spans (intervals identified by t
heir start and end indices). For instance\, the regular spanners are the c
losure under the Relational Algebra (RA) of the regular expressions with c
apture variables\, and the expressive power of the regular spanners is pre
cisely captured by the class of vset-automata - a restricted class of tran
sducers that mark the endpoints of selected spans. In this work\, we embar
k on the investigation of document spanners that can annotate extractions
with auxiliary information such as confidence\, support\, and confidential
ity measures. To this end\, we adopt the abstraction of provenance semirin
gs by Green et al.\, where tuples of a relation are annotated with the ele
ments of a commutative semiring\, and where the annotation propagates thro
ugh the (positive) RA operators via the semiring operators. Hence\, the pr
oposed spanner extension\, referred to as an annotator\, maps every string
into an annotated relation over the spans. As a specific instantiation\,
we explore weighted vset-automata that\, similarly to weighted automata an
d transducers\, attach semiring elements to transitions. We investigate ke
y aspects of expressiveness\, such as the closure under the positive RA\,
and key aspects of computational complexity\, such as the enumeration of a
nnotated answers and their ranked enumeration in the case of numeric semir
ings. For a number of these problems\, fundamental properties of the under
lying semiring\, such as positivity\, are crucial for establishing tractab
ility.\nThis is a joint work with Johannes Doleschal\, Benny Kimelfeld and
Wim Martens.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Subgame Perfect Equilibria in Quantitative Reachability Games - Ma
rie Van Den Bogaard\, ULB
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200228T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200228T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1082
DESCRIPTION:In this talk\, we consider multiplayer games on graphs. In suc
h games\, each player has his own objective\, that does not necessarily cl
ash with the objectives of the other players. In this "non zero-sum" conte
xt\, equilibria are a better suited solution concept than the classical wi
nning strategy notion. We will focus on a refinement of the well-known Nas
h Equilibrium concept: Subgame Perfect Equilibrium (SPE for short)\, wher
e players have to play rationnally in every scenario\, even the ones that
deviate from the planned outcome. We will explain why this refinement is a
relevant solution concept in multiplayer games and show how to handle the
m in quantitative reachability games\, where each player wants to minimize
the number of steps to reach its own target set of vertices.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Extensions of $\\omega$-Regular Languages - Georg Zetsche\, MPI SW
S
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200225T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200225T150000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1088
DESCRIPTION:We consider extensions of monadic second order logic\nover $\\
omega$-words\, which are obtained by adding one\nlanguage that is not $\\o
mega$-regular. We show that\nif the added language $L$ has a neutral lett
er\, then\nthe resulting logic is necessarily undecidable. A\ncorollary is
that the $\\omega$-regular languages are\nthe only decidable Boolean-clos
ed full trio over\n$\\omega$-words. \n\n(Joint work with Mikołaj Bojańcz
yk\, Edon Kelmendi\,\nand Rafał Stefański)
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:TBA - Edwin Hamel-De Le Court
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200327T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200327T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1089
DESCRIPTION:TBA
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reversible Transducers - Luc Dartois\, LACL
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200221T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200221T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1092
DESCRIPTION:Transducers extend automata by adding outputs to the transitio
n\, thus computing functions over words instead of recognizing languages.
Deterministic two-way transducers define the robust class of regular funct
ions which is\, among other good properties\, closed under composition. Ho
wever\, the best known algorithms for composing two-way transducers are ra
ther involved and cause a double exponential blow-up in the size of the in
put machines. This contrasts with the rather direct and polynomial constru
ction for composing one-way machines.\nIn this talk\, I will present the c
lass of reversible transducers\, which are machines that are both determin
istic and co-deterministic. This class enjoys polynomial composition compl
exity\, even in the two-way case.\nAlthough this class is not very express
ive in the one-way scenario\, I will show that any two-way transducer can
be made reversible through a single exponential blow-up. As a consequence\
, the composition of two-way transducers can be done with a single exponen
tial blow-up in the number of states\, enhancing the best known algorithm
from the 60s.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:From Equational Specifications of Algebras with Structure to Varie
ties of Data Languages - Stefan Milius\, Friedrich-Alexander Universität
Erlangen-Nürnberg
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200306T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200306T113000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1104
DESCRIPTION:We present a new category theoretic approach to equationally \
naxiomatizable classes of algebras. This approach is well-suited for the \
ntreatment of algebras equipped with additional computationally relevant \
nstructure\, such as ordered algebras\, continuous algebras\, quantitative
\nalgebras\, nominal algebras\, or profinite algebras. We present a gener
ic \nHSP theorem and a sound and complete equational logic\, which encompa
ss \nnumerous flavors of equational axiomizations studied in the literatur
e. \nIn addition\, we use the generic HSP theorem as a key ingredient to \
nobtain Eilenberg-type correspondences yielding algebraic \ncharacterizati
ons of properties of regular machine behaviours. When \ninstantiated for o
rbit-finite nominal monoids\, the generic HSP theorem \nyields a crucial s
tep for the proof of the first Eilenberg-type variety \ntheorem for data l
anguages.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Automata Learning: An Algebraic Approach - Henning Urbat\, FAU Erl
angen-Nürnberg
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200306T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200306T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1105
DESCRIPTION:We propose a generic framework for learning unknown formal lan
guages of various types (e.g. finite or infinite words\, weighted and nomi
nal languages). Our approach is parametric in a monad T that represents th
e given type of languages and their recognizing algebraic structures. Usin
g the concept of an automata presentation of T-algebras\, we demonstrate t
hat the task of learning a T-recognizable\nlanguage can be reduced to lear
ning an abstract form of algebraic automaton whose transitions are modeled
by a functor. For the important case of adjoint automata\, we devise a le
arning algorithm generalizing Angluin’s L*. The algorithm is phrased in
terms of categorically described extension steps\; we provide for a termin
ation and complexity analysis based on a dedicated notion of finiteness. O
ur framework applies to structures like ω-regular languages that were not
within\nthe scope of existing categorical accounts of automata learning.
In addition\, it yields new generic learning algorithms for several\ntypes
of languages for which no such algorithms were previously known at all\,
including nominal languages with name binding\, and cost functions. This t
alk is based on joint work with Lutz Schröder.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Controlling a random population - Pierre Ohlmann\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200320T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200320T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1107
DESCRIPTION:Bertrand et al. (2017) introduced a model of parameterised\nsy
stems\, where each agent is represented by a finite state system\, and\nst
udied the following control problem: for any number of agents\, does\nther
e exist a controller able to bring all agents to a target state? They\nsho
wed that the problem is decidable and EXPTIME-complete in the\nadversarial
setting\, and posed as an open problem the stochastic setting\,\nwhere th
e agent is represented by a Markov decision process. In this\npaper\, we s
how that the stochastic control problem is decidable. Our\nsolution makes
significant uses of well quasi orders\, of the max-flow min-\ncut theorem\
, and of the theory of regular cost functions.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Assume Guarantee Synthesis for Prompt Linear Temporal Logic - Nath
anaël Fijalkow\, LaBRI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200403T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200403T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1111
DESCRIPTION:An assume guarantee (AG) specification is of the form "Assumpt
ion implies Guarantee". AG Synthesis is the following problem: given an AG
specification\, construct a system satisfying it. \n\nIn this talk I wil
l discuss the case where both Assumptions and Guarantees are given by Prom
pt Linear Temporal Logic (Prompt LTL)\, which is a logic extending LTL by
adding bound requirements such as "every request is answered in bounded ti
me".\n\nThe solution to the AG problem for Prompt LTL will be an invitatio
n to the theory of regular cost functions. \n\n\nJoint work with Bastien M
aubert and Moshe Y. Vardi.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:An Efficient Normalisation Procedure for Linear Temporal Logic - J
avier Esparza
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200410T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200410T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1126
DESCRIPTION:Joint work with Salomon Sickert\n\nIn the mid 80s\, Lichtenste
in\, Pnueli\, and Zuck proved a classical theorem stating that every formu
la of LTL with past operators is equivalent to a formula of the form $\\b
igwedge_{i=1}^n \\G\\F \\varphi_i \\vee \\F\\G \\psi_i $\, where $\\varphi
_i$ and $\\psi_i$ contain only past operators. Some years later\, Chang\,
Manna\, and Pnueli built on this result to derive a similar normal form fo
r the future fragment of LTL. Both normalisation procedures had a non-elem
entary worst-case blow-up\, and followed an involved path from LTL formula
s to counter-free automata to star-free regular expressions and back to LT
L. We improve on both points. We present a purely syntactic normalisation
procedure from LTL to LTL\, with single exponential blow-up\, that can be
implemented in a few dozen lines of Standard ML code. As an application\,
we derive a simple algorithm to translate LTL into deterministic Rabin aut
omata. The algorithm normalises the formula\, translates it into a special
very weak alternating automaton\, and applies a simple determinisation pr
ocedure\, valid only for these special automata.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:An Automaton Group with PSPACE-Complete Word Problem - Jan Philipp
Wächter\, Universität Stuttgart
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200417T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200417T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1130
DESCRIPTION:Finite automata pose an interesting alternative way to present
groups\nand semigroups. Some of these automaton groups became famous for
their\npeculiar properties and have been extensively studied. In addition
to\nthat\, there exists also a line of research on the general properties
of\nthe class of automaton groups.\n\nOne aspect of this research is the s
tudy of algorithmic properties of\nautomaton groups and semigroups. While
many natural algorithmic\ndecision problems have been proven or are genera
lly suspected to be\nundecidable for these classes\, the word problem form
s a notable\nexception. In the group case\, it asks whether a given word i
n the\ngenerators is equal to the neutral element in the group in question
and\nis well-known to be decidable for automaton groups. In fact\, it was
\nobserved in a work by Steinberg published in 2015 that it can be solved\
nin nondeterministic linear space using a straight-forward guess and\nchec
k algorithm. In the same work\, he conjectured that there is an\nautomaton
group with a PSPACE-complete word problem.\n\nIn a recent paper presented
at STACS 2020\, Armin Weiß and I could prove\nthat there indeed is such
an automaton group. To achieve this\, we\ncombined two ideas. The first on
e is a construction introduced by\nDaniele D'Angeli\, Emanuele Rodaro and
me to show that there is an\ninverse automaton semigroup with a PSPACE-com
plete word problem and the\nsecond one is an idea already used by Barringt
on in 1989 to encode NC¹\ncircuits in the group of even permutation over
five elements. In the\ntalk\, we will discuss how Barrington's idea can be
applied in the\ncontext of automaton groups\, which will allow us to prov
e that the\nuniform word problem for automaton groups (were the generating
\nautomaton and\, thus\, the group is part of the input) is PSPACE-\ncompl
ete. Afterwards\, we will also discuss the ideas underlying the\nconstruct
ion to simulate a PSPACE-machine with an invertible automaton\,\nwhich all
ow for extending the result to the non-uniform case. Finally\,\nwe will br
iefly look at related problems such as the compressed word\nproblem for au
tomaton groups.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Unambiguous Separators for Tropical Tree Automata - Thomas Colcomb
et\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200515T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200515T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1133
DESCRIPTION:In this paper we show that given a max-plus automaton (over tr
ees\, and with real weights) computing a function f and a min-plus automat
on (similar) computing a function g such that f ⩽ g\, there exists effec
tively an unambiguous tropical automaton computing h such that f ⩽ h ⩽
g. This generalizes a result of Lombardy and Mairesse of 2006 stating tha
t series which are both max-plus and min-plus rational are unambiguous. Th
is generalization goes in two directions: trees are considered instead of
words\, and separation is established instead of characterization (separat
ion implies characterization). The techniques in the two proofs are very d
ifferent.
LOCATION:Online\, on BigBlueButton (usual link\, available on the mailing
list)
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weakly-unambiguous Parikh automata and their link to holonomic ser
ies - Florent Koechlin
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200507T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200507T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1134
DESCRIPTION:We investigate the connection between properties of formal lan
guages and properties of their generating series\, with a focus on the cla
ss of holonomic power series.\n\nIt is a classical result that regular la
nguages have rational generating series and that the generating series of
unambiguous context-free languages are algebraic. This connection between
automata theory and analytic combinatorics has been successfully exploited
. For instance\, Flajolet used it in the eighties to prove the inherent am
biguity of some context-free languages using criteria from complex analysi
s. \n\nSettling a conjecture of Castiglione and Massazza\, we establish an
interesting link between unambiguous Parikh automata and holonomic power
series\, which also yields characterizations of inherent ambiguity and alg
orithmic byproducts for these automata models.\n\nThis is a joint work wit
h Alin Bostan\, Arnaud Carayol and Cyril Nicaud.
LOCATION:Online\, on BigBlueButton (usual link\, available on the mailing
list)
END:VEVENT
BEGIN:VEVENT
SUMMARY:Single use transducers over infinite alphabets - Mikołaj Bojańcz
yk\, MIMUW
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200522T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200522T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1140
DESCRIPTION:Automata for infinite alphabets\, despite undeniable appeal\,
are a bit of a theoretical mess. Almost all models are non-equivalent as l
anguage recognisers: deterministic/nondeterministic/alternating\, one-way/
two-way\, etc. Also monoids give a different class of languages\, and mso
gives yet another. \n \nIn this talk\, I will describe how the single-use
restriction can bring some order into this zoo. The single-use restriction
says that once an atom from a register is queried\, then that atom disapp
ears. Among our results: a Factorisation Forest Theorem\, a Krohn-Rhodes d
ecomposition\, and a class of "regular" transducers which admits four equi
valent characterisations.\n\nJoint work with Rafał Stefański.
LOCATION:Virtual seminar on BigBlueButton
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Strahler Number of a Parity Game - K. S. Thejaswini\, Universi
ty of Warwick
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200605T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200605T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1149
DESCRIPTION:The Strahler number is a measure of branching complexity of ro
oted trees. We define the Strahler number of a parity game to be the the
smallest Strahler number of the tree of any of its attractor decomposition
s. In this talk\, we will argue that the Strahler number of a parity game
is a robust\, and hence arguably natural\, parameter: it coincides with it
s alternative version based on trees of progress measures and— remarkabl
y—with the register number defined by Lehtinen (2018). \nWe will also lo
ok at how parity games can be solved in quasi-linear space and in time tha
t is polynomial in the number of vertices n and linear in (d/2k)^k \, wher
e d is the number of priorities and k is the Strahler number. This complex
ity is quasi-polynomial because the Strahler number is at most logarithmic
in the number of vertices. This significantly improves the running times
and space achieved for parity games of bounded register number by Lehtinen
(2018) and by Parys (2020).
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:On detectability of finite automata and labeled Petri nets - Kuize
Zhang
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200612T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200612T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1163
DESCRIPTION:Abstract: Detectability is a basic property of partially obser
ved dynamic systems. If a system satisfies such a property\, then one can
use an observed output sequence generated by the system to determine its i
nternal states after some time. This property plays an important role in m
any problems such as state estimation and controller synthesis. Finite aut
omata and labeled Petri nets are two widely-studied models in discrete-eve
nt systems\, which consist of transitions between discrete states driven b
y spontaneous occurrences of events\, and can be seen as abstractions of m
any practical systems. (A supervisory control framework for synthesising c
ontrollers in discrete-event systems was initiated by Ramadge and Wonham i
n the late 1980s.) In this talk\, we introduce recent verification results
on a particular property called strong detectability\, for finite automat
a and labeled Petri nets\, and several related further topics.
LOCATION:Online (BigBlueButton)
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weighted Logics and Weighted Simple Automata for Context-Free Lang
uages of Infinite Words - Sven Dziadek
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200619T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200619T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1164
DESCRIPTION:We investigate weighted context-free languages of infinite wor
ds\, a\ngeneralization of ω-context-free languages (Cohen\, Gold 1977) an
d an\nextension of weighted context-free languages of finite words (Chomsk
y\,\nSchützenberger 1963). As in the theory of formal grammars\, these\nw
eighted languages\, or ω-algebraic series\, can be represented as\nsoluti
ons of ω-algebraic systems of equations and by weighted\nω-pushdown auto
mata.\n\nOur results are threefold. We show that ω-algebraic systems can
be\ntransformed into Greibach normal form. Our second result proves that\n
simple ω-pushdown automata recognize all ω-algebraic series. Simple\npus
hdown automata do not use ε-transitions and can change the stack\nonly by
at most one symbol. We use these results to prove a logical\ncharacteriza
tion of weighted ω-context-free languages in the\nsense of Büchi\, Elgo
t and Trakhtenbrot.\n\nThis is joint work with Manfred Droste and Werner K
uich.
LOCATION:Online on BigBlueButton
END:VEVENT
BEGIN:VEVENT
SUMMARY:About learning automata and weighted automata - Laure Daviaud\, Ci
ty University of London
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200626T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200626T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1170
DESCRIPTION:In this talk\, I will present algorithms to learn deterministi
c finite automata (due to Angluin) and weigthed automata over the usual se
miring R with addition and multiplication (due to Beimel\, Bergadano\, Bsh
outy\, Kushilevitz and Varricchio). I will then present some related open
questions and pinpoint the difficulty that arise when trying to generalise
these algorithms to any semiring.
LOCATION:Held online\, on BigBlueButton
END:VEVENT
BEGIN:VEVENT
SUMMARY:Characterization of computability and complexity classes with diff
erence equations - Olivier Bournez\, LIX
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201009T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201009T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1182
DESCRIPTION:We will discuss the expressive and computational power of Ordi
nary Differential Equations (ODEs). \nWe present the general theory of dis
crete ODEs for computation theory\, we illustrate this with various exampl
es of algorithms\, and we provide several implicit characterizations of co
mplexity and computability classes.
LOCATION:Salle 3052 and online on BigBlueButton
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bidimensional linear recursive sequences and universality of unamb
iguous register automata - Lorenzo Clemente\, Faculty of Mathematics\, Inf
ormatics and Mechanics\, University of Warsaw.
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201016T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201016T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1188
DESCRIPTION:We study the universality and inclusion problems L(A)⊆L(B) f
or register automata over equality data.\nWe show that the universality an
d inclusion problems can be solved in 2-EXPTIME when both automata A\, B a
re without guessing and B is unambiguous\,\nwhich improves on the recent 2
-EXPSPACE upper bound by Mottet and Quaas.\nWe proceed by reducing inclusi
on to universality\, and then universality to the problem of counting the
number of orbits of runs of the automaton.\nWe show that the orbit-countin
g function satisfies a system of bidimensional linear recursive equations
with polynomial coefficients (linrec)\,\nwhich generalises analogous recur
rences for the Stirling numbers of the second kind\,\nand then we show tha
t universality reduces to the zeroness problem for linrec sequences.\nWhil
e such a counting approach is classical and has successfully been applied
to unambiguous finite automata and grammars over finite alphabets\,\nits a
pplication to register automata over infinite alphabets is novel.\n\nWe pr
ovide two algorithms to decide the zeroness problem for the linrec sequenc
es arising from orbit-counting functions.\nBoth algorithms rely on skew po
lynomials. The first algorithm performs variable elimination and has eleme
ntary complexity.\nThe second algorithm relies on the computation of the H
ermite normal form of matrices over a skew polynomial field.\nThis yields
an EXPTIME decision procedure for the zeroness problem\,\nwhich in turn yi
elds the claimed bounds for the universality and inclusion problems of reg
ister automata.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Recognizing Good-for-Games automata: the G2 conjecture - Denis Kup
erberg\, LIP\, ENS Lyon\, CNRS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201106T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201106T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1192
DESCRIPTION:In the setting of regular languages of infinite words\, Good-f
or-Games \n(GFG) automata can be seen as an intermediate formalism between
\ndeterminism and nondeterminism\, with advantages from both worlds. \nIn
deed\, like deterministic automata\, GFG automata enjoy good \ncompositio
nal properties (useful for solving games and composing \nautomata and tree
s) and easy inclusion checks. Like nondeterministic \nautomata\, they can
be exponentially more succinct than deterministic \nautomata. I will focus
in this talk on the following problem: given a \nnondeterministic parity
automaton on infinite words\, is it GFG ? The \ncomplexity of this problem
is one of the main remaining open questions \nconcerning GFG automata\, m
otivated by the potential applications that \nwould come with an efficient
algorithm. After giving the necessary \ncontext\, I will explain the curr
ent understanding on this question\, and \ndescribe a simple polynomial-ti
me algorithm that is conjectured to solve \nthe problem\, but has only bee
n proven correct if the input is a Büchi or \na co-Büchi automaton.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Substitution planar tilings with n-fold rotational symmetry - Vict
or Lutfalla\, LIPN
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201120T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201120T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1195
DESCRIPTION:I will present the tools we used to study tilings that are\nbo
th substitutive and planar (a relaxed version of cut-and-project) in\norde
r to present our main result that there exist planar substitution\ntilings
with 2n-fold rotational symmetry for any odd n.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Coverability in 1-VASS with Disequality Tests - Guillermo Alberto
Perez\, University of Antwerp
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201112T153000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201112T163000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1196
DESCRIPTION:In this talk we will focus on the so-called control-state reac
hability problem (also called the coverability problem) for 1-dimensional
vector addition systems with states (VASS). We show that this problem lies
in NC: the class of problems solvable in polylogarithmic parallel time. W
e will also generalize the problem to allow disequality constraints on tra
nsitions (i.e.\, we allow transitions to be disabled if the accumulated we
ight is equal to a specific value). For this generalization\, we show that
the coverability problem is solvable in polynomial time even though a sho
rtest run may have exponential length.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bisimulation Finiteness of Pushdown Systems Is Elementary - Stefan
Göller\, University of Kassel
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210129T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210129T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1198
DESCRIPTION:It is shown that if a pushdown system is bisimulation equivale
nt to a finite system\, there is already such a finite system whose size i
s elementary in the description size of the pushdown system. As a conseque
nce\, it is elementarily decidable if a pushdown system is bisimulation-fi
nite. This is joint work with Pawel Parys.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pebble Minimization of Polyregular Functions. - Nathan Lhote\, LaB
RI
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201127T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201127T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1199
DESCRIPTION:We show that a polyregular word-to-word function is regular if
and only \nif its output size is at most linear in its input size. Moreov
er a \npolyregular function can be realized by: a transducer with two pebb
les \nif and only if its output has quadratic size in its input\, a transd
ucer \nwith three pebbles if and only if its output has cubic size in its
\ninput\, etc. Moreover the characterization is decidable and\, given a \n
polyregular function\, one can compute a transducer realizing it with the
\nminimal number of pebbles. We apply the result to mso interpretations \n
from words to words. We show that mso interpretations of dimension k \nexa
ctly coincide with k-pebble transductions.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Universality problem for unambiguous Vector Addition Systems with
States - Wojciech Czerwiński\, University of Warsaw
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201030T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201030T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1200
DESCRIPTION:I will show that the universality problem is ExpSpace-complete
for unambiguous VASS\,\nwhich is in strong contrast with Ackermann-comple
teness of the same problem for nondeterministic VASS.\nI also plan to pres
ent some more results concerning the interplay between unambiguity and VAS
S.\n\n(joint work with Diego Figueira and Piotr Hofman)
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rational subsets of Baumslag-Solitar groups - Georg Zetzsche
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201204T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201204T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1204
DESCRIPTION:We consider the rational subset membership problem for Baumsla
g-Solitar \ngroups. These groups form a prominent class in the area of alg
orithmic \ngroup theory\, and they were recently identified as an obstacle
for \nunderstanding the rational subsets of GL(2\,ℚ). We show that rati
onal \nsubset membership for Baumslag-Solitar groups BS(1\,q) with q ≥ 2
is \ndecidable and PSPACE-complete. To this end\, we introduce a word \nr
epresentation of the elements of BS(1\,q): their pointed expansion (PE)\,
\nan annotated q-ary expansion. Seeing subsets of BS(1\,q) as word \nlangu
ages\, this leads to a natural notion of PE-regular subsets of \nBS(1\,q):
these are the subsets of BS(1\,q) whose sets of PE are regular \nlanguage
s. Our proof shows that every rational subset of BS(1\,q) is \nPE-regular.
Since the class of PE-regular subsets of BS(1\,q) is \nwell-equipped with
closure properties\, we obtain further applications of \nthese results. O
ur results imply that (i) emptiness of Boolean \ncombinations of rational
subsets is decidable\, (ii) membership to each \nfixed rational subset of
BS(1\,q) is decidable in logarithmic space\, and \n(iii) it is decidable w
hether a given rational subset is recognizable. \nIn particular\, it is de
cidable whether a given finitely generated \nsubgroup of BS(1\,q) has fini
te index.\n\nThis is joint work with Michaël Cadilhac and Dmitry Chistiko
v.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Holonomic Techniques\, Periods\, and Decision Problems - Joël Oua
knine\, MPI-SWS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201211T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201211T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1205
DESCRIPTION:Holonomic techniques have deep roots going back to Wallis\, Eu
ler\, and Gauss\, and have evolved in modern times as an important subfiel
d of computer algebra\, thanks in large part to the work of Zeilberger and
others over the past three decades. In this talk\, I will give an overvie
w of the area\, and in particular will present a select survey of known an
d original results on decision problems for holonomic sequences and functi
ons. I will also discuss some surprising connections to the theory of peri
ods and exponential periods\, which are classical objects of study in alge
braic geometry and number theory\; in particular\, I will relate the decid
ability of certain decision problems for holonomic sequences to deep conje
ctures about periods and exponential periods\, notably those due to Kontse
vich and Zagier.\n\nParts of this talk will be based on the paper "On Posi
tivity and Minimality for Second-Order Holonomic Sequences"\, https://arxi
v.org/abs/2007.12282 .
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cyclic proofs\, System T and the power of contraction - Damien Pou
s
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20201218T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20201218T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1206
DESCRIPTION:We study a cyclic proof system C over regular expression types
\,\ninspired by linear logic and non-wellfounded proof theory.\nProofs in
C can be seen as strongly typed goto programs. We show that\nthey denote c
omputable total functions and we analyse the relative\nstrength of C and G
ödel's system T.\nIn the general case\, we prove that the two systems cap
ture the same\nfunctions on natural numbers.\nIn the affine case\, i.e.\,
when contraction is removed\, we prove that\nthey capture precisely the pr
imitive recursive functions---providing\nan alternative and more general p
roof of a result by Dal Lago\, about\nan affine version of system T.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Learning automata and transducers: a categorical approach - Daniel
a Petrisan
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210122T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210122T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1268
DESCRIPTION:In this talk we present a categorical approach to learning aut
omata over words\, in the sense of the $L^*$-algorithm of Angluin. This yi
elds a new generic $L^*$-like algorithm which can be instantiated for lear
ning deterministic automata\, automata weighted over fields\, as well as s
ubsequential transducers. The generic nature of our algorithm is obtained
by adopting an approach in which automata are simply functors from a parti
cular category representing words to a "computation category". We establis
h that the sufficient properties for yielding the existence of minimal aut
omata in combination with some additional hypotheses relative to terminati
on ensure the correctness of our generic algorithm.\n\nThis is joint work
with Thomas Colcombet and Riccardo Stabile.
LOCATION:Online
END:VEVENT
BEGIN:VEVENT
SUMMARY:Church Synthesis on Register Automata over Infinite Ordered Domain
s - Ayrat Khalimov
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210115T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210115T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1271
DESCRIPTION:Register automata are finite automata equipped with a finite s
et of registers in which they can store data\, i.e. elements from an infin
ite alphabet\, and compare this data for equality. They provide a simple f
ormalism to specify the behaviour of reactive systems operating data. Init
ially defined with the equality predicate only\, they can be extended to a
llow for comparison of data with regards to a linear order\, like (N\,<) o
r (Q\,<). We study the synthesis problem for those specifications. To that
end\, we extend the classical Church synthesis game to infinite alphabets
: two players\, Adam and Eve\, alternately pick some data\, and Eve wins w
henever their interaction satisfies the specification\, which is a languag
e of infinite words over infinite data alphabet. Unfortunately\, such game
s are undecidable already for specifications described by deterministic re
gister automata. Therefore\, we study one-sided Church games\, where Eve u
ses a finite alphabet but Adam still manipulates data. We show such games
are decidable in exponential time in the number of registers in the specif
ication\, both for Q and N\, are determined\, and strategies\ndescribable
by finite-state register transducers suffice for Eve to win. To obtain thi
s result we study constraint sequences\, which abstract the behaviour of r
egister automata and allow for reduction of Church games to omega-regular
games. Finally\, we apply these results to the transducer-synthesis proble
m.\nI will end the talk with the discussion of bounded synthesis. There\,
specification automata are universal (aka co-nondeterministic)\, and we se
arch for a realizing transducer with an a-priori given number of registers
(hence the term 'bounded synthesis'). This problem is known to be decidab
le for register automata comparing data for equality only\, and we will lo
ok at the challenges arising for the case of (N\,<).\n\n(This is the joint
work by Léo Exibard\, Emmanuel Filiot\, Ayrat Khalimov)
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:2-Valued Logic for SQL on Incomplete Information - Liat Peterfreun
d
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210219T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210219T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1297
DESCRIPTION:The design of SQL is based on a three-valued logic (3VL)\, rat
her than the usual two-valued Boolean logic. This 3VL accommodates the add
itional truth value "unknown" for handling nulls\, representing missing va
lues. This third truth value is viewed as indispensable for SQL expressive
ness\, but is at the same time being criticized a lot for leading to unint
uitive behavior of queries and for being a source of programmer mistakes.\
n\nIn a joint work with Leonid Libkin\, we show that\, contrary to the wid
ely held view\, SQL could have been designed based on the standard two-val
ued logic\, without any loss of expressiveness and without giving up nulls
. We show that conflating unknown\, resulting from conditions referring to
nulls\, with false leads to an equally expressive version of SQL. Queries
written under the two-valued semantics can be efficiently translated into
the standard SQL and thus executed on any existing RDBMS. Our results cov
er the core of the SQL 1999 Standard\, including SELECT-FROM-WHERE-GROUP B
Y-HAVING queries extended with subqueries and IN/EXISTS/ANY/ALL conditions
\, and recursive queries. In addition\, we show that no other many-valued
logic for treating nulls could have possibly led to a more expressive lang
uage.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Successor-Invariant First-Order Logic on Classes of Bounded Degree
- Julien Grange
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210212T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210212T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1298
DESCRIPTION:Successor-invariant first-order logic is the extension of firs
t-order logic where one has access to an additional successor relation on
the elements of the structure\, as long as the validity of formulas doesn'
t depend on the choice of a particular successor.\nIt has been shown by Ro
ssman that this formalism allows to express properties that are not FO-def
inable.\nHowever\, his separating example involves dense classes of struct
ures\, and the expressive power of successor-invariant first-order logic i
s an open question for sparse classes of structures.\nWe prove that when t
he degree is bounded\, successor-invariant first-order logic is no more ex
pressive than first-order logic.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Star-free languages\, first-order transductions and the non-commut
ative λ-calculus - Pierre Pradic
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210319T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210319T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1299
DESCRIPTION:he talk will be based on joint work with Lê Thành Dũng (Tit
o)\nNguyễn.\n\nThis work is part of an exploration of the expressiveness
of the\nsimply-typed λ-calculus (STLC) and related substructural variant
s\n(linear\, affine\, planar) using Church encodings of datatypes. More\ns
pecifically\, we are interested in the connection with automata theory\nfo
r string transductions and languages.\n\nI will first introduce the settin
g and motivate the problems using\nHillebrand and Kanellakis' result stati
ng that the classes of\nSTLC-definable and regular languages coincide. I w
ill then focus on a\nresult stating that star-free languages correspond ex
actly to those\nobtained in a non-commutative refinement of STLC based on
linear logic.\nI will sketch an alternative proof of this result using a s
emantic\nevaluation argument and discuss related work-in-progress concerni
ng\ncharacterizations in the non-commutative λ-calculus of first-order\nr
egular string transductions using planar reversible 2DFTs and\ntree-walkin
g automata.\n\n(the results I will present are based on\nhttps://hal.archi
ves-ouvertes.fr/hal-02476219 and\nhttp://nguyentito.eu/2021-01-links.pdf)
LOCATION:http://perso.ens-lyon.fr/pierre.pradic/slides/2021-03-irif.pdf
END:VEVENT
BEGIN:VEVENT
SUMMARY:Search algorithms for Probabilistic Context-Free Grammars - Nathan
aël Fijalkow
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210312T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210312T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1302
DESCRIPTION:A probabilistic context-free grammar (PCFG) defines a distribu
tion over trees: each (finite) tree has some probability of being generate
d. We consider the following game: a (secret) tree is generated by a PCFG.
The PCFG is known and given as input\, and the goal is to find the tree.
How many equality queries are needed? \nWe'll discuss algorithms for solvi
ng this problem\, using either enumeration or sampling\, and applications
to program synthesis.\n\nJoint (ongoing) work with Pierre Ohlmann and Guil
laume Lagarde.
LOCATION:https://u-paris.zoom.us/rec/share/CF6tuTHp2Y6P2vtynWBE_dDKsv93CiJ
OIBtvg3ujsYCsqvPpjMS6DCY3Wf_BzmUx.GtIj9JDQznwAW_6w Passcode: F504d+s8@?
END:VEVENT
BEGIN:VEVENT
SUMMARY:Three views on numeration systems - Manfred Madritsch\, Universit
é de Lorraine\, CNRS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210305T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210305T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1335
DESCRIPTION:A numeration system associates to each element of a given set
a finite\nword. The best known of these systems is the decimal system\,\nw
hich associates each positive integer with a word of the alphabet\n$\\{0\,
1\,\\ldots\,9\\}$. This idea can easily be generalised to other\npositive
integers as base such as the binary system or the hexadecimal\nsystem.\n\n
The first part deals with signed numeration systems. In these systems\,\nw
e add digits to the alphabet such as the digit $-1$ in the binary\nsystem.
Under certain conditions\, on consecutive digits\, we obtain\nunique repr
esentations. This is related to the concept of abstract\nnumeration system
s. We will study the shift and odometer from the\npoint of view of dynamic
al systems.\n\nDigital restrictions also play an important role in another
numeration\nsystem: the Zeckendorf expansion. This is an example of the l
arger\nclass of numeration systems based on linear recurrent sequences\, w
hich\nwe discuss in the second part. A way to analyse a numeration system
is\nto examine functions operating on the digital representation. The most
\nfamous of these functions is the sum-of-digits function and we\ninvestig
ate it from an analytic point of view.\n\nIn the expansion of a randomly c
hosen real\, we expect each block of\ndigits to occur with the same freque
ncy. This leads to the concept of\nnormal numbers and the related notion o
f uniformly distributed\nsequences. In the last part\, we adopt a probabil
istic point of view\nand construct normal numbers and uniformly distribute
d sequences\nrelated to numeration systems.
LOCATION:Online at https://bbb-front.math.univ-paris-diderot.fr/recherche/
ama-bgy-hx5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:The pseudofinite monadic second order theory of linear order (and
a connection to profinite algebra). - Deacon Linkhorn
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210604T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210604T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1340
DESCRIPTION:The monadic second order theory of a linear order (A\,<) can b
e understood using the first order structure M(A\,<) = (P(A)\,⊆\,<) wher
e P(A) is the powerset of A\, ⊆ is the usual set-theoretic inclusion\, a
nd < is the ordering of (A\,<) given on singleton subsets. By the pseudofi
nite monadic second order theory of linear order we mean the intersection
of the first order theories of the structures M(A\,<) across all finite li
near orders (A\,<).\n\nI will present an explicit axiomatisation of this s
hared theory\, and characterise the non-standard completions (i.e. those a
dmitting infinite models) in terms of residue functions. I will then talk
about a connection with profinite monoids using extended Stone duality. In
particular I will discuss a special case of a theorem due to Gehrke\, Gri
gorieff\, and Pin saying that the free profinite monoid on one generator i
s the extended Stone dual of the Boolean algebra of regular languages over
a singleton alphabet (together with the binary operation of concatenation
).
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Decidability of Reachability in Continuous Time Linear Time
-Invariant Systems - Amaury Pouly\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210402T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210402T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1358
DESCRIPTION:We consider the decidability of state-to-state reachability in
linear time-invariant control systems over continuous time. We analyze th
is problem with respect to the allowable control sets\, which are assumed
to be the image under\na linear map of the unit hypercube (\\emph{i.e.} zo
notopes).\nThis naturally models bounded (sometimes called saturated) cont
rols.\nDecidability of the version of the reachability problem in which\nc
ontrol sets are affine subspaces of R^n is a fundamental result in\ncontro
l theory. We obtain some decidability results in low dimension or when the
spectrum of the matrix is special. We also obtain some decidability condi
tioned on the decidability of the first-order theory of the reals with the
exponential function. Finally we obtain a hardness result for a mid gener
alization of the problem. In this case\, we show that the problem is at le
ast as hard as the Continuous Positivity problem if the control set is a s
ingleton\, or the Nontangential Continuous Positivity problem if the contr
ol set is $[-1\,1]$.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Re-pairing brackets and commutative automata. - Misha Vyalyi
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210423T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210423T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1359
DESCRIPTION:TBA
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tree-to-tree functions - Amina Doumane
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210625T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210625T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1360
DESCRIPTION:We study tree-to-tree transformations that can be defined in f
irst-order logic or monadic second-order logic. We prove a decomposition t
heorem\, which shows that every transformation can be obtained from prime
transformations\, such as tree-to-tree homomorphisms or pre-order traversa
l\, by using combinators such as function composition.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:On Decidability of Time-Bounded Reachability in CTMDPs - Sadegh So
udjani
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210507T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210507T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1362
DESCRIPTION:In this talk\, I discuss the time-bounded reachability problem
for continuous-time Markov decision processes. I show that the problem is
decidable subject to Schanuel’s conjecture. The decision procedure reli
es on the structure of optimal policies and the conditional decidability (
under Schanuel’s conjecture) of the theory of reals extended with expone
ntial and trigonometric functions over bounded domains. I further discuss
that any unconditional decidability result would imply unconditional decid
ability of the bounded continuous Skolem problem\, or equivalently\, the p
roblem of checking if an exponential polynomial has a non-tangential zero
in a bounded interval. The latter problems are also decidable subject to S
chanuel’s conjecture but finding unconditional decision procedures remai
n longstanding open problems. Time permitting\, I can also discuss some al
gorithmic approximate computations using Lyapunov theory of dynamical syst
ems. This talk is based on an ICALP 2020 paper joint with Rupak Majumdar a
nd Mahmoud Salamati at MPI-SWS.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dynamic Membership for regular language - Charles Paperman
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210618T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210618T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1363
DESCRIPTION:We study the dynamic membership problem for regular languages:
fix a language L\, read a word w\, build in time O(|w|) a data structure
indicating if w is in L\, and maintain this structure efficiently under su
bstitution edits on w. We consider this problem on the unit cost RAM model
with logarithmic world length\, where the problem always has a solution i
n O(log |w| / log log |w|). We show that the problem is in O(log log |w|)
for languages in an algebraically-defined class QSG\, and that it is in O(
1) for another class QLZG. We show that languages not in QSG admit a reduc
tion from the prefix problem for a cyclic group\, so that they require \\O
mega(log n/ log log n) operations in the worst case\; and that QSG languag
es not in QLZG admit a reduction from the prefix problem for the monoid U_
1\, which we conjecture cannot be maintained in O(1). This yields a condit
ional trichotomy. We also investigate intermediate cases between O(1) and
O(log log n). Our results are shown via the dynamic word problem for monoi
ds and semigroups\, for which we also give a classification. We thus solve
open problems of the paper of Skovbjerg Frandsen\, Miltersen\, and Skyum
on the dynamic word problem\, and additionally cover regular languages.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Positive first-order logic on words - Denis Kuperberg\, CNRS\, ENS
de Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210430T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210430T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1368
DESCRIPTION:I will present FO+\, a restriction of first-order logic where
letters are required to appear positively\, and the alphabet is partially
ordered\, for instance by inclusion order if letters are sets of atoms. Re
stricting predicates to appear positively is very natural when considering
for instance logics with fixed points\, or various extensions of regular
languages. Here we will ask a syntax versus semantics question: FO+-defina
ble languages are monotone in the letters\, but can every FO-definable mon
otone language be defined in FO+ ? On general structures\, Lyndon's theore
m gives such a syntax/semantics equivalence for monotone first-order formu
las\, but it is known to fail on finite structures. We will see that it al
so fails on finite words\, giving a much simpler proof for the failure of
Lyndon's theorem on finite structures. Finally we will investigate whether
FO+-definability is decidable for regular languages on ordered alphabets.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:A Complexity Approach to Tree Algebras: the Bounded Case - Arthur
Jaquard
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210416T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210416T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1369
DESCRIPTION:The talk is based on joint work with Thomas Colcombet.\nWe ini
tiate a study of the expressive power of tree algebras\, and more generall
y infinitely sorted algebras\, based on their asymptotic complexity.\n\nTr
ee algebras in many of their forms\, such as clones\, hyperclones\, operad
s\, etc\, as well as other kind of algebras\, are infinitely sorted: the c
arrier is a multi sorted set indexed by a parameter that can be interprete
d as the number of variables or hole types. Finite such algebras - meaning
when all sorts are finite - can be classified depending on the asymptotic
size of the carrier sets as function of the parameter\, that we call the
complexity of the algebra. This naturally defines the notions of algebras
of bounded\, linear\, polynomial\, exponential or doubly exponential compl
exity...\n\nOur main result precisely characterizes the tree algebras of b
ounded complexity based on the languages that they recognize as Boolean cl
osures of simple languages. Along the way\, we prove that such algebras th
at are syntactic are exactly those in which\, as soon as there are suffici
ently many variables\, the elements are invariant under permutation of the
variables.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the decidability of dynamical properties of addtive cellular au
tomata - Enrico Formenti
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210521T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210521T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1378
DESCRIPTION:In this talk we are going to prove the decidability of several
properties on the dynamics\nof additive cellular automata over finite abe
lian groups. In the first part\, we prove the\nresults for a restricted cl
ass of additive CA\, namely the linear CA by using a new ‘ad hoc’ resu
lt\nfrom algebra. In the second part\, we show how to lift the all the pro
perties to the whole class of\nadditive CA over finite abelian groups.
LOCATION:https://u-paris.zoom.us/rec/share/CBacDMMIJL2XuVNP7bx9V23Y1lpOsU0
Dql1SwglYizke_yn6MOTtQEwXgFOVqZs.4RJmUCKgDVogKWAj Passcode: k$o$L92E6J
END:VEVENT
BEGIN:VEVENT
SUMMARY:On the Size of Finite Rational Matrix Semigroups - Jonathan Tanner
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210528T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210528T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1395
DESCRIPTION:Let n be a positive integer and M a set of rational n×n-matri
ces such that M generates a finite multiplicative semigroup. We show that
any matrix in the semigroup is a product of matrices in M whose length is
at most O(n2logn)\, where g(n) is the maximum order of finite groups over
rational n×n-matrices. This result implies algorithms with an elementary
running time for deciding finiteness of weighted automata over the rationa
ls and for deciding reachability in affine integer vector addition systems
with states with the finite monoid property.
LOCATION:https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx
5-3rl
END:VEVENT
BEGIN:VEVENT
SUMMARY:Optimal Transformations of Games and Automata using Muller Conditi
ons - Antonio Casares
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210702T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210702T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1404
DESCRIPTION:Automata and games over infinite words are widely used in veri
fication and synthesis of reactive systems. Several different kinds of acc
eptance conditions can be used in these systems\, which may differ in thei
r complexity and expressive power. For their simplicity and usefulness\, p
arity conditions are of special relevance. However\, in many applications
such as LTL-synthesis\, the automata that are obtained in the first place
use more complex conditions (Muller conditions) and we have to transform t
hem in parity ones.\n\nIn this talk\, I will present a construction that t
akes as input a Muller automaton and transforms it into a parity automaton
in an optimal way. More precisely\, the resulting parity automaton has mi
nimal size and uses a minimal number of priorities among those automata th
at admit a locally bijective morphism to the original Muller automaton. Th
is transformation and the optimality result can also be applied to games a
nd other types of transition systems.\n\nWe show two applications: an impr
ovement on the determinisation of Büchi automata into deterministic parit
y automata and characterisations of automata that admit parity\, Rabin or
Streett conditions in top of them.\n\nThis is joint work with Thomas Colco
mbet and Nathanaël Fijalkow\, and it will appear at ICALP 2021.
LOCATION:Hybride : Salle 3052 et BBB (https://bbb-front.math.univ-paris-di
derot.fr/recherche/ama-bgy-hx5-3rl)
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lacon- and Shrub-Decompositions: Characterizing First-Order Trans
ductions of Bounded Expansion Classes - Jan Dreier
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210611T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210611T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1406
DESCRIPTION:The concept of bounded expansion provides a robust way to capt
ure sparse \ngraph classes with interesting algorithmic properties. Most n
otably\, \nevery problem definable in first-order logic can be solved in l
inear \ntime on bounded expansion graph classes. First-order interpretatio
ns and \ntransductions of sparse graph classes lead to more general\, dens
e graph \nclasses that seem to inherit many of the nice algorithmic proper
ties of \ntheir sparse counterparts.\n\nThe leading question of this talk
is: "How can we generalize the \nbeautiful existing algorithmic results of
sparse graphs to dense \ngraphs?" We start with an overview over sparse a
nd dense graph classes\nand then introduce lacon- and shrub-decompositions
. We show that dense\ngraph classes can be exactly characterized by having
a sparse lacon- or \nshrub-decoposition. If one could efficiently compute
such a \ndecomposition then one could solve every problem definable in \n
first-order logic in linear time on these classes.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Derived terms without derivation - Jacques Sakarovitch\, IRIF\, CN
RS & Télécom Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211001T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211001T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1446
DESCRIPTION:The topic of this talk is\, once again\, the transformation of
rational expressions into finite automata\, a much laboured subject. In o
ur last joint work\, Sylvain Lombardy and I take a shifted perspective on
the derivation of expressions method (due to Brzozowski and Antimirov) whi
ch reveals that there is indeed no derivation involved. This broadens the
scope of the method to expressions over non free monoids.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Active learning automata with syntactic queries - Jan Otop\, Unive
rsity of Wrocław
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211203T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211203T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1451
DESCRIPTION:Regular languages can be actively learned with membership and
equivalence queries in polynomial time. The learning algorithm\, called th
e L^* algorithm\, constructs iteratively the right congruence relation of
a given regular language L\, and returns the minimal DFA recognizing L. Th
e L^* algorithm has been adapted to various types of automata: tree automa
ta\, weighted automata\, nominal automata. However\, an extension to infin
ite-word automata has been elusive.\nIn this talk\, I will present an exte
nsion of the active learning framework\, in which the algorithm can ask sy
ntactic queries about the automaton representing a given infinite-word lan
guage.\n\nFirst\, I will discuss why extending L^*\, which asks only seman
tic queries\, to infinite-words languages is difficult. Next\, I will pres
ent an alternative approach\; instead of learning some automaton for a hid
den language\, we assume that there is a hidden automaton and the algorith
m is supposed to learn an equivalent automaton.\nIn this approach\, the le
arning algorithm is allowed to ask standard semantic queries (membership a
nd equivalence) and loop-index queries regarding the structure of the hidd
en automaton. These queries do not reveal the full structure of the automa
ton and hence do not trivialize the learning task.\n\nIn the extended fram
ework\, there are polynomial-time learning algorithms for various types of
infinite-word automata: deterministic Buechi automata\, LimSup-automata\,
deterministic parity automata and limit-average automata.\n\nFinally\, th
e idea to incorporate syntactic queries can be adapted to the pushdown fra
mework\; I will briefly discuss the learning algorithm for deterministic v
isibly pushdown automata.
LOCATION:Salle 3052 (Online)
END:VEVENT
BEGIN:VEVENT
SUMMARY:Algebraically characterising first-order logic with neighbour - Am
aldev Manuel\, Indian Institute of Technology Goa
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211015T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211015T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1452
DESCRIPTION:We give an algebraic characterisation of first-order logic wit
h the neighbour relation\, on finite words. For this\, we consider languag
es of finite words over alphabets with an involution on them. The natural
algebras for such languages are involution semigroups. To characterise the
logic\, we define a special kind of semidirect product of involution sem
igroups\, called the locally hermitian product. The characterisation theor
em for FO with neighbour states that a language is definable in the logic
if and only if it is recognised by a locally hermitian product of an aperi
odic commutative involution semigroup\, and a locally trivial involution s
emigroup.\nWe then define the notion of involution varieties of languages\
, namely classes of languages closed under Boolean operations\, quotients\
, involution\, and inverse images of involutory morphisms. An Eilenberg-ty
pe correspondence is established between involution varieties of languages
and pseudovarieties of involution semigroups. This is joint work with Dh
ruv Nevatia.
LOCATION:Salle 3052 (Online) https://u-paris.zoom.us/j/87690991231?pwd=QjN
4QUJKdExOMXp3a1MrQTNNL1RuZz09
END:VEVENT
BEGIN:VEVENT
SUMMARY:Telling Everything. Information Quotients in Games with Communicat
ion - Dietmar Berwanger\, LSV
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211022T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211022T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1455
DESCRIPTION:We present a model of games with imperfect information that fe
atures explicit communication actions\, by which a player can send her ent
ire observation history to another player. Such full-information protocols
are common in asynchronous distributed systems\, here we consider a synch
ronous setting and cast it as a game on word-automatic trees. The informat
ion structures arising from such games are again automatic trees\, but the
ir branching degree can be unbounded\, and then the synthesis problem beco
mes challenging. We present a method for constructing a finite bisimulatio
n quotient for a representative subcase\, which solves the problem effecti
vely. The construction is a guess\; if time allows\, we will speculate on
how to find such quotients systematically.\n\nThe talk is based on joint w
ork (in progress) with Laurent Doyen\; a part of the material is presented
in [D. Berwanger\, L. Doyen (2019): Observation and distinction in infini
te games\, https://arxiv.org/abs/1809.05978]
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Undefined - Nathan Grosshans
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220325T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220325T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1457
DESCRIPTION:
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:FO-separation of regular languages over words of ordinal length -
Thomas Colcombet
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211008T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211008T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1463
DESCRIPTION:We show that the existence of a first-order formula separating
two monadic second order formulas over countable ordinal words is decidab
le. \nThis extends the work of Henckell and Almeida on finite words\, and
of Place and Zeitoun on $\\omega$-words. \nThis is a joint work with Rémi
Morvan and Sam van Gool
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Orbit-finite-dimensional vector spaces\, with applications to weig
hted register automata - Bartek Klin
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220204T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220204T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1467
DESCRIPTION:I will discuss vector spaces spanned by orbit-finite sets. The
se spaces are infinite-dimensional\, but their sets of dimensions are so h
ighly symmetric that the spaces have many properties enjoyed by finitely-d
imensional spaces.\n\nApplications of this include a decision procedure fo
r equivalence of weighted register automata\, which are the common general
ization of weighted automata and register automata for infinite alphabets.
The algorithm runs in exponential time\, and in polynomial time for a fix
ed number of registers. As a special case\, we can decide\, with the same
complexity\, language equivalence for unambiguous register automata.\n\n(J
oint work with Mikołaj Bojańczyk and Joshua Moerman.)
LOCATION:Salle 3052 (Online)
END:VEVENT
BEGIN:VEVENT
SUMMARY:How undecidable are HyperLTL and HyperCTL*? - Marie Fortin\, Unive
rsity of Liverpool
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211210T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211210T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1477
DESCRIPTION:Temporal logics for the specification of information-flow prop
erties are able to express relations between multiple executions of a syst
em. Two of the most important such logics are HyperLTL and HyperCTL*\, whi
ch generalise LTL and CTL* by trace quantification. It is known that this
expressiveness comes at a price\, i.e.\, satisfiability is undecidable for
both logics. We settle the exact complexity of these problems\, showing t
hat both are in fact highly undecidable: we prove that HyperLTL satisfiabi
lity is \\Sigma_1^1-complete and HyperCTL* satisfiability is \\Sigma_1^2-c
omplete. To prove \\Sigma_1^2 membership for HyperCTL*\, we prove that eve
ry satisfiable HyperCTL* formula has a model that is equinumerous to the c
ontinuum\, the first upper bound of this kind. We prove this bound to be t
ight.\nThis is joint work with Louwe B. Kuijer\, Patrick Totzke and Martin
Zimmermann.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Extensive-form games with incentive stage-bidding - Stéphane Le R
oux
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211126T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211126T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1478
DESCRIPTION:To the classical way of playing in finite extensive-form games
\, we add a\nbidding mechanism: at each node of the game tree\, each non-c
ontrolling\nplayer bids some amount of utility for one subgame. When the c
ontroller\nchooses one subgame\, the utilities that were bid for this subg
ame are\ntransferred to her.\n\nThe notion of subgame perfect equilibrium
(SPE) is naturally extended to\nthese bidding games\, and they always alwa
ys exist like in the classical\ngames. They also enjoy new properties:\n-
If the game tree is binary-branching\, payoff-sum-maximizing SPE always\ne
xist.\n- If the game involves only two players\, all SPE are\npayoff-sum-m
aximizing with the same payoff-tuple\, which is called the\nbidding value
of the game. \n- This value is computable\, whereas SPE payoff-tuples are
not even\ncontinuous in classical games.\n\nThis is joint work with Valen
tin Goranko
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:The Fine-Grained Complexity of Answering Database Queries - Nofar
Carmeli\, ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20211029T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20211029T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1494
DESCRIPTION:We wish to identify the queries that can be solved with close
to optimal time guarantees over relational databases. Computing all query
answers requires at least linear time before the first answer (to read the
input and determine the answer's existence)\, and then we must allow enou
gh time to print all answers (which may be many). Thus\, we aspire to achi
eve linear preprocessing time and constant or logarithmic time per answer.
\nA known dichotomy classifies Conjunctive Queries into those that admit s
uch enumeration and those that do not: the main difficulty of query answer
ing is joining tables\, which can be done efficiently if and only if the j
oin query is acyclic. However\, the join query usually does not appear in
a vacuum\; for example\, it may be part of a larger query\, or it may be a
pplied to a database with dependencies. We show how to use this context fo
r more efficient computation and study how the complexity changes in these
settings. Next\, we aspire for an even more powerful solution for query a
nswering: a structure that simulates an array containing the query answers
. Such a structure can be used for example to enumerate all answers in a s
tatistically meaningful order or to efficiently compute a boxplot of query
answers. We call this simulation random access and study for which querie
s random access can be achieved with near-optimal guarantees.\nOur results
are accompanied by conditional lower bounds showing that our algorithms c
an be applied to all tractable queries in some cases. Among our results\,
we show that a union of tractable Conjunctive Queries may be intractable w
.r.t. random access\, but a union of intractable Conjunctive Queries may b
e tractable w.r.t. enumeration.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Extending Reactive Synthesis to Infinite Data Domains through Mach
ines with Registers - Léo Exibard
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220105T161500
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220105T171500
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1560
DESCRIPTION:In reactive synthesis\, the goal is to automatically generate
an implementation from a specification of the reactive and non-terminating
input/output behaviours of a system. Specifications are usually modelled
as logical formulas or automata over infinite sequences of signals (omega
‑words)\, while implementations are represented as transducers. In the c
lassical setting\, the set of signals is assumed to be finite.\n\nThe aim
of this talk is to investigate the case of infinite alphabets. Correspondi
ngly\, executions are modelled as data omega-words. In this context\, we s
tudy specifications and implementations respectively given as automata and
transducers extended with a finite set of registers\, used to store and c
ompare data values. We consider different instances\, depending on whether
the specification is nondeterministic\, universal (a.k.a. co-nondetermini
stic) or deterministic: contrary to the finite-alphabet case\, those class
es are expressively distinct.\n\nWhen the number of registers of the targe
t implementation is unbounded\, the synthesis problem is undecidable\, whi
le decidability is recovered in the deterministic case. In the bounded set
ting\, undecidability still holds for non-deterministic specifications\, b
ut decidability is recovered for universal ones.\n\nThe study was initiall
y conducted over data domains with the equality predicate only\, but the t
echniques can be lifted to the dense order (Q\,<) and so-called oligomorph
ic data domains\, over which register automata behave in an omega-regular
way. A further exploration of the problem allows to extend the results to
the discrete order (N\,<)\, where the behaviours can be regularly approxim
ated. Finally\, decidability can be transferred to the case of words with
the prefix relation (A^*\,<) through a notion of reducibility between doma
ins.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Demonstration of Awali 2.1\, a library for weighted automata and t
ransducers. - Victor Marsault
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220121T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220121T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1577
DESCRIPTION:Awali is a software suite for computing with finite weighted a
utomata and\ntransducers with any number of tapes. Many algorithms are im
plemented\nincluding most of the classical ones. Automata and transducers
may be weighted\nover a classical number sets (N\,Z\,Q\,R\,C\,Z/nZ) but a
lso over several other\nweightsets (such as the tropical semirings).\n\nAw
ali may be accessed in C++ (awalidyn\, or directly using templates) or in\
nPython (awalipy). Awali can also be used interactively from its command-
line\ninterface (Cora) or using awalipy together with Jupyter\, a top-leve
l Python\ninterpreter.\n\nAwali may be downloaded from http://vaucanson-pr
oject.org/Awali/2.1/ and I'll\nbe happy to address possible installation i
ssues after the presentation.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:On computing the algebraic closure of matrix groups - Klara Nosan
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220211T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220211T153000
DTSTAMP;VALUE=DATE-TIME:20220119T070300Z
UID:1579
DESCRIPTION:We consider the problem of computing the Zariski closure of a
finitely generated group of matrices. Algorithms for this problem have be
en applied in automata theory and program analysis\, e.g.\, for showing d
ecidability of the language emptiness problem for quantum automata and for
computing polynomial invariants for affine programs. \n\nIn this talk we
introduce the problem of computing the Zariski closure and describe an exi
sting algorithm\, due to Derksen\, Jeandel and Koiran\, before moving to o
ur main result\, which is to obtain an upper bound on the degree of the po
lynomials that define the Zariski closure. Having an a priori bound allows
us to give a simple algorithm for the problem\, via linear algebra\, simi
lar to Karr's algorithm for obtaining affine invariants for affine program
s.
LOCATION:Salle 3052
END:VEVENT
END:VCALENDAR