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

DOI10.1016/J.IC.2022.104889MaRDI QIDQ2084774zbMATH OpenOpenAlexFDO

Authors 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

Boolean satisfiability problemChomsky grammarscontext-sensitive fusion grammarsfusion grammars with forbidden contextgraph coloring problemgraph transformationpost correspondence problemrecursively enumerable languages

Mathematics Subject Classification ID

Recommendations

• Context-sensitive fusion grammars are universal
• Transformation of Turing machines into context-dependent fusion grammars
• Transformation of variants of Petri nets into context-dependent fusion grammars
• Fusion grammars: a novel approach to the generation of graph languages
• Transformation of Petri nets into context-dependent fusion grammars

Cites work

• A software package for chemically inspired graph transformation
• A system of graph grammars which generates all recursively enumerable sets of labelled graphs
• A variant of a recursively unsolvable problem
• Context-sensitive fusion grammars are universal
• Fusion grammars: a novel approach to the generation of graph languages
• Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 1701353 (Why is no real title available?)
• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 2060078 (Why is no real title available?)
• scientific article; zbMATH DE number 234035 (Why is no real title available?)
• Introduction to graph grammars with applications to semantic networks
• Recent advances in formal languages and applications.
• Reducibility among combinatorial problems
• Relating DNA computing and splitting/fusion grammars
• Splicing/fusion grammars and their relation to hypergraph grammars
• The complexity of theorem-proving procedures
• Transformation of Petri nets into context-dependent fusion grammars
• Transformation of Turing machines into context-dependent fusion grammars

Cited in

(4)

• Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020
• Transformation of Turing machines into context-dependent fusion grammars
• On decidability and expressive power of fusion grammars
• Context-sensitive fusion grammars are universal

Describes a project that uses

Uses Software

• MedOlDatschgerl

This page was built for publication: Context-sensitive fusion grammars and fusion grammars with forbidden context are universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084774)