Interval-valued computations and their connection to PSPACE
| dc.contributor.author | Vályi, Sándor | |
| dc.contributor.author | Nagy, Benedek | |
| dc.date.accessioned | 2012-06-14T12:42:02Z | |
| dc.date.available | 2012-06-14T12:42:02Z | |
| dc.date.issued | 2012-06-14 | |
| dc.date.year | 2008 | |
| dc.description | copyright 2008 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.tcs.2007.12.013 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.format.firstpage | 208 | en_US |
| dc.format.issue | 3 | en_US |
| dc.format.lastpage | 222 | en_US |
| dc.format.pages | 15 | en_US |
| dc.format.volume | 384 | en_US |
| dc.identifier.issn | 0304-3975 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/65 | |
| dc.language.iso | en | en_US |
| dc.subject | massively parallel computing | en_US |
| dc.subject | interval-valued computing | en_US |
| dc.title | Interval-valued computations and their connection to PSPACE | en_US |
| dc.title.journal | Theoretical Computer Science | en_US |
| dc.type.class | Article | en_US |
| dc.type.specification | Scientific | en_US |