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

graph coloring problemgraph transformationrecursively enumerable languagesBoolean satisfiability problemcontext-sensitive fusion grammarspost correspondence problemChomsky grammarsfusion grammars with forbidden context

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

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

• 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 7453088 (Why is no real title available?)
• scientific article; zbMATH DE number 234035 (Why is no real title available?)
• 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
• 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

Cited in

(2)

• Context-sensitive fusion grammars are universal
• Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020

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)