%0 Conference Proceedings
%T On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages
%+ Umeå University, Sweden
%+ University of Victoria [Canada] (UVIC)
%A Bensch, Suna
%A Hoeberechts, Maia
%Z Part 2: Contributed Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 19th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Milano, Italy
%Y Giovanni Pighizzini
%Y Cezar Câmpeanu
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10316
%P 65-76
%8 2017-07-03
%D 2017
%R 10.1007/978-3-319-60252-3_5
%K Tree adjoining languages
%K Head grammar languages
%K Degree of nondeterminism
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01657017/document
%2 https://inria.hal.science/hal-01657017/file/440206_1_En_5_Chapter.pdf
%L hal-01657017
%U https://inria.hal.science/hal-01657017
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10316