Umeå University's logo

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
Acyclic contextual hyperedge replacement: decidability of acyclicity and generative power
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
University of Bremen, Bremen, Germany.
Universität der Bundeswehr München, Neubiberg, Germany.
2022 (English)In: Graph Transformation: 15th International Conference, ICGT 2022, Held as Part of STAF 2022, Nantes, France, July 7–8, 2022, Proceedings / [ed] Nicolas Behr; Daniel Strüber, Cham: Springer, 2022, p. 3-19Conference paper, Published paper (Refereed)
Abstract [en]

Graph grammars based on contextual hyperedge replacement (CHR)  extend the generative power of the well-known hyperedge replacement  (HR) grammars to an extent that makes them useful for practical  modeling. Recent work has shown that acyclicity is a key condition for  parsing CHR grammars efficiently. In this paper we show that acyclicity of CHR grammars is decidable  and that the generative power of  acyclic CHR grammars lies strictly between that of HR grammars and  unrestricted CHR grammars.

Place, publisher, year, edition, pages
Cham: Springer, 2022. p. 3-19
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13349
Keywords [en]
Graph grammar, Hyperedge replacement, Contextual hyperedge replacement, Acyclicity, Decidability, Generative power
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-194089DOI: 10.1007/978-3-031-09843-7_1ISI: 000870300100001Scopus ID: 2-s2.0-85135030138ISBN: 978-3-031-09842-0 (print)ISBN: 978-3-031-09843-7 (electronic)OAI: oai:DiVA.org:umu-194089DiVA, id: diva2:1653726
Conference
15th International Conference on Graph Transformation, ICGT 2022, held as Part of STAF 2022, Nantes, France, July 7-8, 2022.
Available from: 2022-04-24 Created: 2022-04-24 Last updated: 2023-09-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Drewes, Frank

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 150 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