Skip to Main content Skip to Navigation
Conference papers

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

https://hal.inria.fr/hal-01657017
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:44:48 AM
Last modification on : Thursday, July 19, 2018 - 8:58:05 PM

File

440206_1_En_5_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Suna Bensch, Maia Hoeberechts. On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.65-76, ⟨10.1007/978-3-319-60252-3_5⟩. ⟨hal-01657017⟩

Share

Metrics

Record views

115

Files downloads

79