@Article{         gilleron:inria-00538882,
  Author        = "Gilleron, R{\'e}mi and Tison, Sophie",
  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.}",
  affiliation   = "GRAPPA - LIFL , Laboratoire d'Informatique Fondamentale de Lille - LIFL",
  audience      = "internationale",
  date-added    = "2012-10-01 10:09:17 +0000",
  date-modified = "2012-10-26 09:23:45 +0000",
  hal_id        = "inria-00538882",
  Journal       = "Fundamenta Informaticae",
  Keywords      = "rewriting systems and preservation of regularity",
  Language      = "Anglais",
  Number        = "1/2",
  Pages         = "157--176",
  Publisher     = "IOS Press",
  Title         = "{Regular Tree Languages and Rewrite Systems}",
  URL           = "http://hal.inria.fr/inria-00538882",
  Volume        = "24",
  Year          = "1995",
  bdsk-url-1    = "http://hal.inria.fr/inria-00538882",
  File          = "Regular Tree Languages and Rewrite Systems - Gilleron, Tison (0) (0) - a - a - d.pdf"
}

@Article{ gilleron:inria-00538882, Author = "Gilleron, R{\'e}mi and Tison, Sophie", 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.}", affiliation = "GRAPPA - LIFL , Laboratoire d'Informatique Fondamentale de Lille - LIFL", audience = "internationale", date-added = "2012-10-01 10:09:17 +0000", date-modified = "2012-10-26 09:23:45 +0000", hal_id = "inria-00538882", Journal = "Fundamenta Informaticae", Keywords = "rewriting systems and preservation of regularity", Language = "Anglais", Number = "1/2", Pages = "157--176", Publisher = "IOS Press", Title = "{Regular Tree Languages and Rewrite Systems}", URL = "http://hal.inria.fr/inria-00538882", Volume = "24", Year = "1995", bdsk-url-1 = "http://hal.inria.fr/inria-00538882", File = "Regular Tree Languages and Rewrite Systems - Gilleron, Tison (0) (0) - a - a - d.pdf" }