umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The Generative Power of Delegation Networks
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Natural and Formal Languages)
Leiden Institute of Advanced Computer Science.
2015 (Engelska)Ingår i: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 245, s. 78s. 213-258Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A device that generates trees over a ranked alphabet, together with an interpretation of the symbols in that alphabet as functions or relations on some domain, generates subsets of that domain. 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 contained in the IO-hierarchy.

Ort, förlag, år, upplaga, sidor
2015. Vol. 245, s. 78s. 213-258
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-101493DOI: 10.1016/j.ic.2015.04.005ISI: 000368899100014OAI: oai:DiVA.org:umu-101493DiVA, id: diva2:799737
Tillgänglig från: 2015-03-31 Skapad: 2015-03-31 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Drewes, Frank

Sök vidare i DiVA

Av författaren/redaktören
Drewes, Frank
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Information and Computation
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 759 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf