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
The Generative Power of Delegation Networks
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
Leiden Institute of Advanced Computer Science.
2012 (English)Report (Other academic)
Abstract [en]

A device that generates trees over a ranked alphabet ∑, together with an interpretation of the symbols in ∑ as functions or relations on a domain A, generates subsets of A. This concept of tree-based generators is well known and essentially already present in the seminal paper by Mezei and Wright from 1967. A delegation network is a system consisting of a finite set of such generators that can "delegate" parts of the generation process to each other. It can be viewed as consisting of an (extended) IO context-free tree grammar and an interpretation. We investigate the language-theoretic properties of these systems and establish several characterizations of the generated languages. In particular, we obtain results in the style of Mezei and Wright. We also study the hierarchy of tree language classes obtained by iterating the concept of delegation, and show that this hierarchy is properly contained in the closure of the regular tree languages under nondeterministic macro tree transductions, but not in the IO-hierarchy.

Place, publisher, year, edition, pages
Umeå: Department of Computing Science, Umeå University , 2012. , 78 p.
Series
UMINF, ISSN 0348-0542 ; 12.15
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-57943OAI: oai:DiVA.org:umu-57943DiVA: diva2:545814
Available from: 2012-08-22 Created: 2012-08-21 Last updated: 2012-08-22Bibliographically approved

Open Access in DiVA

fulltext(3297 kB)226 downloads
File information
File name FULLTEXT02.pdfFile size 3297 kBChecksum SHA-512
77f6c98ecc1518c27f0808bedb406a2d2f8e1d04430058fcb2ba6dee262b2485a21542c66e76ad63ab0818bec42420ab0b62e438e0cf4cfd35260d93909eee62
Type fulltextMimetype application/pdf

Authority records BETA

Drewes, Frank

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 226 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 84 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