Regular Tree Languages and Rewrite Systems

Abstract : We present a collection of results on regular tree languages and rewrite systems. Moreover we prove the undecidability of the preservation of regularity by rewrite systems. More precisely we prove that it is undecidable whether or not for a set E of equations the set E(R) congruence closure of set R is a regular tree language whenever R is a regular tree language. It is equally undecidable whether or not for a confluent and terminating rewrite system S the set S(R) of ground S-normal forms of set R is a regular tree language whenever R is a regular tree language. Finally we study fragments of the theory of ground term algebras modulo congruence generated by a set of equations which can be compiled in a terminating, confluent rewrite system which preserves regularity.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 1995, 24 (1/2), pp.157--176
Liste complète des métadonnées

https://hal.inria.fr/inria-00538882
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:48:39
Dernière modification le : mardi 24 avril 2018 - 13:51:17

Identifiants

  • HAL Id : inria-00538882, version 1

Collections

Citation

Rémi Gilleron, Sophie Tison. Regular Tree Languages and Rewrite Systems. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 1995, 24 (1/2), pp.157--176. 〈inria-00538882〉

Partager

Métriques

Consultations de la notice

230