Characterizing PSPACE with Shallow Non-Confluent P Systems

摘要: In P systems with active membranes, the question of understanding power non-confluence within a polynomial time bound is still an open problem. It known that, for shallow systems, that is, only one level nesting, allows them to solve conjecturally harder problems than confluent thus reaching $$\mathbf{PSPACE }$$ . Here we show not bound, but actually exact characterization. Therefore, endowed by equal gained when non-elementary membrane division and depth are allowed, suggesting connection between roles nesting depth.