A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars

Abstract : Tree languages are powerful tools for the representation and schematization of infinite sets of terms for various purposes (unification theory, verification and specification ...). In order to extend the regular tree language framework, more complex formalisms have been developed. In this paper, we focus on Tree Synchronized Grammars and Primal Grammars which introduce specific control structures to represent non regular sets of terms. We propose a common unified framework in order to achieve the membership test for these particular languages. Thanks to a proof system, we provide a full operational framework, that allows us to transform tree grammars into Prolog programs (as it already exists for word grammars with DCG) whose goal is to recognize terms of the corresponding language.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.227-262
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958984
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:56:14
Dernière modification le : samedi 3 mars 2018 - 01:04:58
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:08:14

Fichier

dm050115.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958984, version 1

Collections

Citation

Frédéric Saubion, Igor Stéphan. A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.227-262. 〈hal-00958984〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

317