Context-sensitive fusion grammars are universal

DOI10.1007/978-3-030-40608-0_19zbMath1437.68085OpenAlexW3007936102MaRDI QIDQ782583

Aaron Lye

Publication date: 27 July 2020

Full work available at URL: https://doi.org/10.1007/978-3-030-40608-0_19

zbMATH Keywords

recursively enumerable languagesPost correspondence problemgraph transformationChomsky grammarcontext-sensitive fusion grammars

Mathematics Subject Classification ID

Hypergraphs (05C65) Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Related Items (2)

Deciding non-emptiness of hypergraph languages generated by connection-preserving fusion grammars is NP-complete ⋮ Context-sensitive fusion grammars and fusion grammars with forbidden context are universal

This page was built for publication: Context-sensitive fusion grammars are universal