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

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2002-01, Vol.5 (1), p.227-262
Main Authors: Saubion, Frédéric, Stéphan, Igor
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.300