Valérie Gouranton, Pierre Réty and Helmut Seidl. Synchronized Tree Languages Revisited and New Applications. In Furio Honsell and Marino Miculan, editors, Foundations of Software Science and Computation Structures, volume 2030 of Lecture Notes in Computer Science, pages 214-229, Genova, Italy, April 2001. Springer.

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 $\mathnormal {L}_{1}$ (synchronized), $\mathnormal {L}_{2}$ (regular), $Rel(\mathnormal {L}_{1})$ ⊆ $\mathnormal {L}_{2}$ 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.

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com