Seminars

Links' Seminars and Public Events Add to google calendar
2016
Fri 18th Nov
10:30 am
12:00 pm
Add event to google
Florent Capelli Links Seminar
"Lille-Salle B21"
Fri 18th Nov
 all day
Add event to google
Florent Capelli visit
Tue 8th Nov
2:30 pm
4:30 pm
Add event to google
Seminar Link by Helmut Seidl: "Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable"
Abstract:

We show that equivalence of deterministic top-down tree-to-string transducers is decidable,
thus solving a long standing open problem in formal language theory.
We also present efficient algorithms for subclasses:
polynomial time for total transducers with unary output alphabet (over a given top-down regular domain language),
and co-randomized polynomial time for linear transducers, these results are obtained using techniques from multi-linear algebra.
For our main result, we prove that equivalence can be certified by means of inductive invariants using polynomial ideals.
This allows us to construct two semi-algorithms, one searching for a proof of equivalence, one for a witness of non-equivalence.
"Lille-Salle B31 "
Mon 7th Nov
2:00 pm
4:00 pm
Add event to google
PhD defense Adrien Boiret
Fri 4th Nov
 all day
Add event to google
colis general meeting
Show in Google map
Paris

Lien Permanent pour cet article : https://team.inria.fr/links/fr/seminars/