umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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. Department of Computing Science.
Department of Computer Science, University of Victoria, Victoria, Canada.
2017 (English)In: Descriptional Complexity of Formal Systems - 19th {IFIP} {WG}, International Conference, (DCFS) 2017 / [ed] Giovanni Pighizzini, Cezar Campeanu, 2017, Vol. 10316, 65-76 p.Conference 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. Vol. 10316, 65-76 p.
Series
Lecture Notes in Computer Science, 10316
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-137253DOI: 10.1007/978-3-319-60252-3ISBN: 978-3-319-60251-6 (print)OAI: oai:DiVA.org:umu-137253DiVA: diva2:1117143
Conference
Descriptional Complexity of Formal Systems (DCFS)
Available from: 2017-06-28 Created: 2017-06-28 Last updated: 2017-06-28

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 1 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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