Synchronized Tree Languages Revisited and New Applications

Valerie Gouranton, Pierre Rety, Helmut Seidl

Keywords : tree-tuple language, rewriting, concurrency.

Abstract:
We present a new formulation for tree-tuple synchronized languages,
much simpler than the existing one. This new formulation
allows us to prove stronger structural results.
As a consequence, synchronized languages give rise to new
applications:
 - to rewriting: given tree languages L1 (synchronized), L2 (regular),
   checking whether Rel(L1) is a subset of L2 is decidable for several
   rewrite-like relations Rel.
 - to concurrency: we prove decidability of the logic EF for a process 
   calculus allowing some bounded form of communication.
Consequently, the absence of deadlocks is decidable.