Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958984
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:56:14 PM
Last modification on : Friday, July 10, 2020 - 10:52:02 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:08:14 PM

File

dm050115.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

152

Files downloads

1166