Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems

2014/01/01 by Niall Murphy, Damien Woods
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced biosensing and bioanalysis techniques #Computer science #DNA and Biological Computing #Materials science #Mathematics #Quantum-Dot Cellular Automata #cs.CC

paper · pdf · doi:10.3233/fi-2014-1095

published as Fundamenta Informaticae, 134(1-2):129-152. 2014 · 28 pages, 1 figure

openalex publication_date 2014/01/01 · arxiv created 2014/12/10 · arxiv updated 2014/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks

Citations

• Computational Complexity
• Nondeterministic Space is Closed under Complementation
• Recursively enumerable sets of positive integers and their decision problems
• Parity, circuits, and the polynomial-time hierarchy