|
Nyíregyházi Egyetem Tudományos Elektronikus Adattár >
Természettudományi és Informatikai Kar >
Matematika és Informatika Intézet >
Matematika Intézet - Folyóiratcikkek >
Ezzel az azonosítóval hivatkozhat erre a dokumentumra forrásmegjelölésben vagy hiperhivatkozás esetén:
https://tea.nye.hu/handle/123456789/65
|
| Besorolás: | Article |
| Jelleg: | Scientific |
| Szerzők: | Vályi, Sándor
Nagy, Benedek |
| Cím: | Interval-valued computations and their connection to PSPACE |
| Folyóirat címe: | Theoretical Computer Science |
| Kötet/Évfolyam: | 384 |
| Füzet/Szám: | 3 |
| Utolsó oldal : | 222 |
| Megjelenés éve /(ideje): | 2008 |
| Oldalszám: | 15 |
| ISSN: | 0304-3975 |
| Nyelv: | en |
| URI : | http://hdl.handle.net/123456789/65 |
| Kulcsszavak: | massively parallel computing
interval-valued computing |
| Absztrakt: | 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. |
| Megjegyzés: | copyright 2008 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.tcs.2007.12.013 |
| Ebben a gyűjteményben: | Matematika Intézet - Folyóiratcikkek
|
Minden dokumentum, ami a TEA rendszerben szerepel, szerzői jogokkal védett. Minden jog fenntartva!
|
