Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • 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 power of local graph expansion grammars with and without additional restrictions
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
Technical University of Munich, TUM School of Computation, Information and Technology, Munich, Germany.
2024 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 1015, article id 114763Article in journal (Refereed) Published
Abstract [en]

We study graph expansion grammars, a type of graph grammar that has recently been introduced with motivations in natural language processing. Graph expansion generalizes the well-known hyperedge replacement. In contrast to the latter, the former is able to generate graph languages of unbounded treewidth, like the set of all graphs. In an earlier paper, the complexity of the membership problem of the generated languages was studied, the main result being a polynomial parsing algorithm for local DAG expansion grammars (there called local DAG expansion grammars), a subclass of graph expansion grammars that generates directed acyclic graphs. Here, we study the generative power of local graph expansion grammars. While they, un- restricted, are able to simulate Turing machines, we identify natural restrictions that give rise to a pumping lemma and ensure that the generated languages have regular path languages as well as a semi-linear Parikh image. 

Place, publisher, year, edition, pages
Elsevier, 2024. Vol. 1015, article id 114763
Keywords [en]
graph grammar, hyperedge replacement, graph expansion grammar, generative power
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-228142DOI: 10.1016/j.tcs.2024.114763ISI: 001296881100001Scopus ID: 2-s2.0-85203023465OAI: oai:DiVA.org:umu-228142DiVA, id: diva2:1886514
Projects
WASP NEST project STING – Synthesis and analysis with Transducers and Invertible Neural Generators
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Available from: 2024-08-01 Created: 2024-08-01 Last updated: 2024-09-16Bibliographically approved

Open Access in DiVA

fulltext(1010 kB)48 downloads
File information
File name FULLTEXT01.pdfFile size 1010 kBChecksum SHA-512
149ee61a3fbde93d0f244a627a504712405eb3877a1261c4307bdb879e63cc37b0a23cce0083c7ec8a7524f8a246aaf59a08381c98bd7d37086de7682326f326
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Drewes, Frank

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
In the same journal
Theoretical Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 48 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

doi
urn-nbn

Altmetric score

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

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