Context-sensitive fusion grammars and fusion grammars with forbidden context are universal
type: Item
instance of: scholarly article
title: Context-sensitive fusion grammars and fusion grammars with forbidden context are universal
author: Aaron Lye
published in: Information and Computation
publication date: 2022-10-13T00:00:00Z
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 7601282
zbMATH Keywords: graph transformation
zbMATH Keywords: context-sensitive fusion grammars
zbMATH Keywords: fusion grammars with forbidden context
zbMATH Keywords: recursively enumerable languages
zbMATH Keywords: Chomsky grammars
zbMATH Keywords: post correspondence problem
zbMATH Keywords: Boolean satisfiability problem
zbMATH Keywords: graph coloring problem
describes a project that uses: MedOlDatschgerl
MaRDI profile type: MaRDI publication profile
full work available at URL: j.ic.2022.104889
OpenAlex ID: W4220953522
cites work: Q4458322
cites work: Q3735714
cites work: Graph structure and monadic second-order logic. A language-theoretic approach
cites work: Fusion grammars: a novel approach to the generation of graph languages
cites work: Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing
cites work: A software package for chemically inspired graph transformation
cites work: Relating DNA computing and splitting/fusion grammars
cites work: Q4223673
cites work: A system of graph grammars which generates all recursively enumerable sets of labelled graphs
cites work: Introduction to graph grammars with applications to semantic networks
cites work: Q5287535
cites work: Recent advances in formal languages and applications.
cites work: Q2769432
cites work: Handbook of Graph Grammars and Computing by Graph Transformation
cites work: Splicing/fusion grammars and their relation to hypergraph grammars
cites work: Transformation of Petri nets into context-dependent fusion grammars
cites work: Transformation of Turing machines into context-dependent fusion grammars
cites work: Context-sensitive fusion grammars are universal
cites work: A variant of a recursively unsolvable problem
cites work: The complexity of theorem-proving procedures
cites work: Reducibility among combinatorial problems
DOI: 10.1016/J.IC.2022.104889
Recommended article: Context-sensitive fusion grammars are universal
Recommended article: Transformation of Turing machines into context-dependent fusion grammars
Recommended article: Transformation of variants of Petri nets into context-dependent fusion grammars
Recommended article: Fusion grammars: a novel approach to the generation of graph languages
Recommended article: Transformation of Petri nets into context-dependent fusion grammars
description: scientific article; zbMATH DE number 7601282