Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
LALBLC: a program testing the equivalence of dpda's
du groupe Graphes et Logique

Date 2013-04-30  11:00-12:00
TitreLALBLC: a program testing the equivalence of dpda's 
RésuméWe present a preliminar version of the program "LALBLC" (i.e. LA=LB? Let us Compute). The equivalence problem for dpda consists in deciding, for two given deterministic pushdown automata A,B, whether they recognize the same language. It was proved in [TCS 2001, G.S.] that this problem is decidable by means of some complete proof systems. The program LALBLC gives, in some sense, life to the above completeness proof: on an input A,B, the program computes either a proof of their equivalence (w.r.t. to the system D5 of the above reference) or computes a witness of their non-equivalence (i.e. a word that belongs to the symmetric difference of the two languages). We shall outline the main mathematical objects that are manipulated as well as the main functions performed over these objects. We shall also describe some experimental results obtained so far. The talk is based on an ongoing, joint, work with P. Henry. 
LieuSalle 076 
OrateurGéraud Sénizergues 
Emailges@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index