Murphy, Niall and Woods, Damien (2014) Uniformity is weaker than semiuniformity for some membrane systems. Fundamenta Informaticae, 134 (12). pp. 129152. ISSN 18758681

Download (350kB)
 Preview

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 wellunderstood, 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 semiuniformity, 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 wellknown and used in Boolean circuit complexity, while the latter notion is frequently found in literature on natureinspired 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 semiuniformity 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 semiuniform 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 semiuniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively.
Item Type:  Article 

Keywords:  membranes systems; computational complexity; uniform families; semiuniform families; tally languages; 
Academic Unit:  Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute 
Item ID:  12407 
Identification Number:  https://doi.org/10.3233/FI20141095 
Depositing User:  Damien Woods 
Date Deposited:  10 Feb 2020 18:12 
Journal or Publication Title:  Fundamenta Informaticae 
Publisher:  IOS Press 
Refereed:  Yes 
URI: 
Repository Staff Only(login required)
Item control page 
Downloads
Downloads per month over past year