Classes of Tree Homomorphisms with Decidable Preservation of Regularity - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Classes of Tree Homomorphisms with Decidable Preservation of Regularity

Résumé

Decidability of regularity preservation by a homomorphism is a well known open problem for regular tree languages. Two interesting subclasses of this problem are considered: first, it is proved that regularity preservation is decidable in polynomial time when the domain language is constructed over a monadic signature, i.e., over a signature where all symbols have arity 0 or 1. Second, decidability is proved for the case where non-linearity of the homomorphism is restricted to the root node (or nodes of bounded depth) of any input term. The latter result is obtained by proving decidability of this problem: Given a set of terms with regular constraints on the variables, is its set of ground instances regular? This extends previous results where regular constraints where not considered.
Fichier non déposé

Dates et versions

hal-00243123 , version 1 (06-02-2008)

Identifiants

  • HAL Id : hal-00243123 , version 1

Citer

Guillem Godoy, Sebastian Maneth, Sophie Tison. Classes of Tree Homomorphisms with Decidable Preservation of Regularity. FOSSACS'08, Apr 2008, Hungary. pp.127-141. ⟨hal-00243123⟩
116 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More