Automata and formal languages

• Decidability of the equivalence problem for deterministic pushdown automata.
  (LaBRI internal report nr 1161-97).
  A very short version has been published in the proceedings ICALP'97, LNCS 1256.
  A short version is the next paper.
  A generalized version is report 1183-97 below.
  A long version is the fourth item of this list.
  A simplified version is the 9-th item of this list.

• Decidability of the equivalence problem for deterministic pushdown automata.
  (Short version, Proceedings of INFINITY'97, published in Electronic Notes in Theoretical Computer Science)
• Decidability of the bisimulation problem for equational graphs of finite out-degree, version 1 (1997).
  (LaBRI internal report nr 1183-97)
  Decidability of the bisimulation problem for equational graphs of finite out-degree, version 2 (August 2000).
• L(A) = L(B)?
  (Corrected, improved and generalized version (22/4/98) of report 1161-97).
  
• Complete formal systems for equivalence problems.
  (Synthesis paper.Invited talk at MCU'98).
• T(A) = T(B)?.
  (LaBRI internal report nr 1209-99. Short version accepted at ICALP'99).
  

• Le problème de l'équivalence des automates à pile déterministes est décidable.
  (Texte de vulgarisation, en français, niveau: licence d'informatique. A paraître dans CNRS-info).
• Some applications of the decidability of dpda's equivalence.
  (Invited talk at MCU'01; corrected version)
• L(A)=L(B)? A simplified decidability proof.
  (2001, To appear in Theoretical Computer Science)
• Invited talk given at ICALP'02.
  (reception of Goedel prize)

Talk given at FMI, Stuttgart (.pdf).
Extended version of previous talk
• The equivalence problem for t-turn DPDA is co-NP.
  (LaBRI internal report nr 1297-03. Short version accepted at ICALP'03)
• LALBLC: a program testing the equivalence of dpda's
  here.