Closure of Tree Automata Languages under Innermost Rewriting

Adria Gascon 1 Guillem Godoy 1 Florent Jacquemard 2
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Preservation of regularity by a term rewriting system (TRS) states that the set of reachable terms from a tree automata (TA) language (aka regular term set) is also a TA language. It is an important and useful property, and there have been many works on identifying classes of TRS ensuring it; unfortunately, regularity is not preserved for restricted classes of TRS like shallow TRS. Nevertheless, this property has not been studied for important strategies of rewriting like the innermost strategy -- which corresponds to the {\em call by value} computation of programming languages. We prove that the set of innermost-reachable terms from a TA language by a shallow TRS is not necessarily regular, but it can be recognized by a TA with equality and disequality constraints between brothers. As a consequence we conclude decidability of regularity of the reachable set of terms from a TA language by innermost rewriting and shallow TRS. This result is in contrast with plain (not necessarily innermost) rewriting for which we prove undecidability. We also show that, like for plain rewriting, innermost rewriting with linear and right-shallow TRS preserves regularity.
Type de document :
Communication dans un congrès
Middeldorp, Aart. 8th International Workshop on Reduction Strategies in Rewriting and Programming (WRS), Jul 2008, Hagenberg, Austria. Elsevier, 237, pp.23-38, 2008, Electronic Notes in Theoretical Computer Science. 〈http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B75H1-4VXW9BM-3&_user=10&_coverDate=04%2F04%2F2009&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=976e2294a5625d24b1268e55f91e14e7&searchtype=a〉. 〈10.1016/j.entcs.2009.03.033〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00578966
Contributeur : Florent Jacquemard <>
Soumis le : mardi 22 mars 2011 - 17:39:49
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 23 juin 2011 - 02:56:58

Fichier

btregularity-wrs-HAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Adria Gascon, Guillem Godoy, Florent Jacquemard. Closure of Tree Automata Languages under Innermost Rewriting. Middeldorp, Aart. 8th International Workshop on Reduction Strategies in Rewriting and Programming (WRS), Jul 2008, Hagenberg, Austria. Elsevier, 237, pp.23-38, 2008, Electronic Notes in Theoretical Computer Science. 〈http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B75H1-4VXW9BM-3&_user=10&_coverDate=04%2F04%2F2009&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=976e2294a5625d24b1268e55f91e14e7&searchtype=a〉. 〈10.1016/j.entcs.2009.03.033〉. 〈inria-00578966〉

Partager

Métriques

Consultations de la notice

178

Téléchargements de fichiers

132