LOGIC AND ARITHMETIC OPERATIONS WITH A CONSTANT NUMBER OF STEPS IN MEMBRANE COMPUTING
| Autor: | Akihiro Fujiwara, Takeshi Tateishi |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | International Journal of Foundations of Computer Science. 22:547-564 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054111008222 |
| Popis: | In the present paper, we propose P systems that work in a constant number of steps. We first propose two P systems for computing multiple input logic functions. An input of the logic functions is a set of n binary numbers of m bits, and an output is a binary number defined by the logic functions. The first and second P systems compute AND and EX-OR functions for the input, and both of the P systems work in a constant number of steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(mn). Next, we propose a P system for the addition of two binary numbers of m bits. The P system works in a constant number of steps by using O(m) types of objects, a constant number of membranes and evolution rules of size O(m2). We also introduce a P system that computes the addition of two vectors of n binary numbers of m bits by using the above P system as a sub-system. The P system for vector addition works in a constant number of steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(m2n). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|