umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Ocean Networks Canada and Department of Computer Science, University of Victoria, Victoria, Canada.
2017 (English)In: Descriptional Complexity of Formal Systems: 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017, Proceedings / [ed] Giovanni Pighizzini, Cezar Câmpeanu, 2017, 65-76 p.Conference paper, Published paper (Refereed)
Abstract [en]

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. 

Place, publisher, year, edition, pages
2017. 65-76 p.
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, E-ISSN 1611-3349 ; 10316
Keyword [en]
Tree adjoining languages, Head grammar languages, Degree of nondeterminism
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-137253DOI: 10.1007/978-3-319-60252-3_5Scopus ID: 2-s2.0-85022346852ISBN: 978-3-319-60251-6 (print)ISBN: 978-3-319-60252-3 (electronic)OAI: oai:DiVA.org:umu-137253DiVA: diva2:1117143
Conference
19th International Conference of Descriptional Complexity of Formal Systems (DCFS 2017), 2017, Milano, Italy, July 3–5, 2017
Available from: 2017-06-28 Created: 2017-06-28 Last updated: 2017-11-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Bensch, Suna
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 111 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf