Context-sensitive fusion grammars and fusion grammars with forbidden context are universal

DOI10.1016/j.ic.2022.104889OpenAlexW4220953522MaRDI QIDQ2084774

Aaron Lye

Publication date: 13 October 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104889

zbMATH Keywords

Chomsky grammarspost correspondence problemrecursively enumerable languagesgraph coloring problemgraph transformationBoolean satisfiability problemcontext-sensitive fusion grammarsfusion grammars with forbidden context

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020

Uses Software

• MedOlDatschgerl

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing
• Context-sensitive fusion grammars are universal
• Introduction to graph grammars with applications to semantic networks
• A system of graph grammars which generates all recursively enumerable sets of labelled graphs
• Splicing/fusion grammars and their relation to hypergraph grammars
• Transformation of Petri nets into context-dependent fusion grammars
• Relating DNA computing and splitting/fusion grammars
• Recent advances in formal languages and applications.
• A Software Package for Chemically Inspired Graph Transformation
• Handbook of Graph Grammars and Computing by Graph Transformation
• Fusion Grammars: A Novel Approach to the Generation of Graph Languages
• Reducibility among Combinatorial Problems
• The complexity of theorem-proving procedures
• A variant of a recursively unsolvable problem