From regulated rewriting to computing with membranes: collapsing hierarchies

DOI10.1016/j.tcs.2003.08.006zbMath1070.68057OpenAlexW1993832215MaRDI QIDQ1884943

Rudolf Freund, Gheorghe Păun, Carlos Martín-Vide

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.08.006

zbMATH Keywords

P systemMembrane computingRecursively enumerable languageMatrix grammarRegulated rewritingGraph-controlled grammarNon-terminal complexityProgrammed grammarRegister machine

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Related Items (11)

Three ``quantum algorithms to solve 3-SAT ⋮ Language generating alphabetic flat splicing P systems ⋮ Extended spiking neural P systems with white hole rules and their red-green variants ⋮ Rewriting P Systems with Flat-Splicing Rules ⋮ P systems with active membranes: Trading time for space ⋮ Results on catalytic and evolution-communication P systems ⋮ Computationally universal P systems without priorities: Two catalysts are sufficient ⋮ (UREM) P Systems with a Quantum-Like Behavior: Background, Definition, and Computational Power ⋮ P SYSTEMS WITH PROTEINS ON MEMBRANES: A SURVEY ⋮ \(P\) systems with active membranes and without polarizations ⋮ On the computational completeness of matrix simple semi-conditional grammars

Cites Work

• Remarks on blind and partially blind one-way multicounter machines
• Petri net algorithms in the theory of matrix grammars
• Computing with membranes
• Generalized P-systems with splicing and cutting/recombination
• On the power of membrane division in P systems
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• COMPUTING WITH MEMBRANES (P SYSTEMS): A VARIANT
• MEMBRANE COMPUTING AND ONE-WAY FUNCTIONS
• Programmed Grammars and Classes of Formal Languages
• Bicolored digraph grammar systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: From regulated rewriting to computing with membranes: collapsing hierarchies