Details

Autor(en) / Beteiligte

• Bensch, Suna
• Hoeberechts, Maia

Titel

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

Ist Teil von

• Descriptional Complexity of Formal Systems, 2017, p.65-76

Ort / Verlag

Cham: Springer International Publishing

Erscheinungsjahr

2017

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

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