Összesen 1 találat.
#/oldal:
Részletezés:
Rendezés:

1.

001-es BibID:BIBFORM005692
Első szerző:Nagy Benedek (informatikus, matematikus)
Cím:Interval-valued computations and their connection with PSPACE / Benedek Nagy, Sándor Vályi
Dátum:2008
Megjegyzések:At the conference CiE 2005, the first author introduced a new model for analog computations, namely interval-valued computations. In this model, computations work on the so-called interval-valued bytes, which are special subsets of the interval [0, 1) rather than a finite sequence of bits. The question was posed there, which complexity is needed to solve PSPACE-complete problems in this paradigm. In this paper, after formalizing the computational model, we answer this question. We show that the validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. As a consequence, all polynomial space problems are decidable by a polynomial interval-valued computation. Furthermore, it is proven that PSPACE coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation.
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
újelvű számítások
intervallum-érték
bonyolultságelmélet
Algorithmic complexity
Parallel computing
New computing paradigms
interval-valued computing
unconvential computing
Megjelenés:Theoretical Computer Science. - 394 : 3 (2008), p. 208-222. -
További szerzők:Vályi Sándor (1968-) (matematikus, informatikus)
Internet cím:DOI
elektronikus változat
elektronikus változat
Borító:
Rekordok letöltése1