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

DOI10.1016/J.IC.2022.104889OpenAlexW4220953522MaRDI QIDQ2084774FDOQ2084774

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)

Cites Work

• Reducibility among combinatorial problems
• Title not available (Why is that?)
• Graph structure and monadic second-order logic. A language-theoretic approach
• The complexity of theorem-proving procedures
• A variant of a recursively unsolvable problem
• Title not available (Why is that?)
• Handbook of Graph Grammars and Computing by Graph Transformation
• Title not available (Why is that?)
• Recent advances in formal languages and applications.
• Title not available (Why is that?)
• A system of graph grammars which generates all recursively enumerable sets of labelled graphs
• Title not available (Why is that?)
• Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing
• Fusion grammars: a novel approach to the generation of graph languages
• Title not available (Why is that?)
• Context-sensitive fusion grammars are universal
• Introduction to graph grammars with applications to semantic networks
• Splicing/fusion grammars and their relation to hypergraph grammars
• A software package for chemically inspired graph transformation
• Transformation of Petri nets into context-dependent fusion grammars
• Relating DNA computing and splitting/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

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)