Proofs and reachability problem for ground rewrite systems

Abstract : The different reachability problems for ground rewrite systems are decidable[OY86], [DEGI89]. We prove these results using ground tree transducers of [DATI85] and wellknown algorithms on recognizable tree languages in order to obtain efficient algorithms. We introduce and study derivation proofs to describe the sequences of rules used to reduce a term t in a term t' for a given ground rewrite system S and sketch how compute a derivation proof in linear time. Moreover, we study the same problem for recognizable tree languages.
Type de document :
Communication dans un congrès
Aspects and Prospects of Theoretical Computer Science, 6th International Meeting of Young Computer Scientists, IMYCS'90, 1990, Prag, Czech Republic. Springer Verlag, 464, pp.120-129, 1990, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00538874
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:47:51
Dernière modification le : jeudi 11 janvier 2018 - 06:20:12

Identifiants

  • HAL Id : inria-00538874, version 1

Collections

Citation

Jean-Luc Coquidé, Rémi Gilleron. Proofs and reachability problem for ground rewrite systems. Aspects and Prospects of Theoretical Computer Science, 6th International Meeting of Young Computer Scientists, IMYCS'90, 1990, Prag, Czech Republic. Springer Verlag, 464, pp.120-129, 1990, Lecture Notes in Computer Science. 〈inria-00538874〉

Partager

Métriques

Consultations de la notice

120