Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: oracles

Sortuj według:

Ogranicz wyniki do:

Membrane Division, Oracles, and the Counting Hierarchy

Leporati A., Manzoni L., Mauri G., Porreca A. E., Zandron C.

Fundamenta Informaticae

2015

Vol. 138, nr 1/2

97--111

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to PPP = P#P, the class of problems solvable in polynomial time by deterministic Turingmachines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between PPP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k.

Computability in Type-2 Objects with Well-Behaved Type-1 Oracles is p-Normal

Tourlakis G.

Fundamenta Informaticae

2001

Vol. 48, nr 1

83-91

We show that computability in a type-2 object is p-normal if type-1 partial inputs are computed by ``well-behaved oracles''