On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages

Abstract : The degree of nondeterminism is a measure of syntactic complexity which was investigated for parallel and sequential rewriting systems. In this paper, we consider the degree of nondeterminsm for tree adjoining grammars and their languages and head grammars and their languages. We show that a degree of nondeterminism of 2 suffices for both formalisms in order to generate all languages in their respective language families. Furthermore, we show that deterministic tree adjoining grammars (those with degree of nondeterminism equal to 1), can generate non-context-free languages, in contrast to deterministic head grammars which can only generate languages containing a single word.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.65-76, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657017
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:48
Dernière modification le : mercredi 6 décembre 2017 - 13:46:15

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Suna Bensch, Maia Hoeberechts. On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.65-76, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_5〉. 〈hal-01657017〉

Partager

Métriques

Consultations de la notice

7