RECORD
Uniformity is weaker than semi-uniformity for some membrane systems
Computational Complexity · Submitted 10 Dec 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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 and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. | background 0.76 | 0.35 | 0.02 | asserted 0.88 |
| s1 | Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks and tile assembly systems, and there are many others. | background 1.00 | 0.05 | 0.01 | asserted 1.00 |
| s2 | However, in such models there are actually two distinct kinds of uniformity condition. | background 0.96 | 0.13 | 0.02 | asserted 1.00 |
| s3 | The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s4 | The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). | background 1.00 | 0.07 | 0.02 | asserted 1.00 |
| s5 | The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s6 | Are these two notions distinct? | gap 0.68 | 0.05 | 0.02 | unclear 0.97 |
| s7 | For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. | background 0.98 | 0.07 | 0.03 | asserted 0.99 |
| s8 | In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. | background 0.74 | 0.88 | 0.04 | asserted 1.00 |
| s9 | Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. | result 0.61 | 0.96 | 0.92 | asserted 1.00 |
| s10 | This solves a known open problem in the theory of membrane systems. | interpretation 0.74 | 0.73 | 0.16 | asserted 1.00 |
| s11 | We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively. | contribution 0.64 | 0.93 | 0.10 | asserted 0.74 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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 and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.