Frédéric Saubion ; Igor Stéphan - A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars

dmtcs:300 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5 -
A Unified Framework to Compute over Tree Synchronized Grammars and Primal GrammarsArticle

Authors: Frédéric Saubion ORCID1; Igor Stéphan 1

  • 1 Laboratoire d'Etudes et de Recherche en Informatique d'Angers

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.

Volume: Vol. 5
Published on: January 1, 2002
Imported on: March 26, 2015
Keywords: Proof Systems,Prolog Implementation,Tree Grammars,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

2 Documents citing this article

Consultation statistics

This page has been seen 244 times.
This article's PDF has been downloaded 305 times.