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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2002-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/170 |
| _version_ | 1818028755466059776 |
|---|---|
| author | Frédéric Saubion Igor Stéphan |
| author_facet | Frédéric Saubion Igor Stéphan |
| author_sort | Frédéric Saubion |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T05:08:50Z |
| format | Article |
| id | doaj.art-d0534375dd8c4186b612c953f1876fac |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-12-10T05:08:50Z |
| publishDate | 2002-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-d0534375dd8c4186b612c953f1876fac2022-12-22T02:01:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80502002-12-0151A Unified Framework to Compute over Tree Synchronized Grammars and Primal GrammarsFrédéric SaubionIgor StéphanTree 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.http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/170 |
| spellingShingle | Frédéric Saubion Igor Stéphan A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars Discrete Mathematics & Theoretical Computer Science |
| title | A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars |
| title_full | A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars |
| title_fullStr | A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars |
| title_full_unstemmed | A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars |
| title_short | A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars |
| title_sort | unified framework to compute over tree synchronized grammars and primal grammars |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/170 |
| work_keys_str_mv | AT fredericsaubion aunifiedframeworktocomputeovertreesynchronizedgrammarsandprimalgrammars AT igorstephan aunifiedframeworktocomputeovertreesynchronizedgrammarsandprimalgrammars AT fredericsaubion unifiedframeworktocomputeovertreesynchronizedgrammarsandprimalgrammars AT igorstephan unifiedframeworktocomputeovertreesynchronizedgrammarsandprimalgrammars |