Shallow laconic P systems can count
| Autor: | Claudio Zandron, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Alberto Leporati |
|---|---|
| Přispěvatelé: | Leporati, Alberto, Manzoni, Luca, Mauri, Giancarlo, Porreca, Antonio E., Zandron, Claudio, Leporati, A, Manzoni, L, Mauri, G, Porreca, A, Zandron, C |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Class (set theory) computational complexity Counting Computational complexity theory Applied Mathematics Computation P systems INF/01 - INFORMATICA ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI membrane computing Computational Theory and Mathematics Laconic P system Theory of computation Shallow P system Complexity class Send-in rule Membrane computing Mathematics |
| Popis: | Uniform families of shallow P systems with active membranes and charges are known to characterize the complexity class $$\textsc {P}^{\#\textsf {P}}$$, since this kind of P systems are able to “count” the number of objects sent out by the dividing membranes. Such a power is absent in monodirectional systems, where no send-in rules are allowed: in this case, only languages in $$\textsc {P}^{\textsf {NP}}_\parallel $$ can be recognized. Here, we show that even a tiny amount of communication (namely, allowing only a single send-in per membrane during the computation) is sufficient to achieve the ability to count and solve all problems in the class $$\textsc {P}^{\#\textsf {P}}_\parallel $$, where all queries are performed independently. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|