Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00538882
Contributor : Rémi Gilleron <>
Submitted on : Tuesday, November 23, 2010 - 2:48:39 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM

Identifiers

  • 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⟩

Share

Metrics

Record views

311