Interval-valued computations and their connection to PSPACE

dc.contributor.authorVályi, Sándor
dc.contributor.authorNagy, Benedek
dc.date.accessioned2012-06-14T12:42:02Z
dc.date.available2012-06-14T12:42:02Z
dc.date.issued2012-06-14
dc.date.year2008
dc.descriptioncopyright 2008 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.tcs.2007.12.013en_US
dc.description.abstractAt 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.firstpage208en_US
dc.format.issue3en_US
dc.format.lastpage222en_US
dc.format.pages15en_US
dc.format.volume384en_US
dc.identifier.issn0304-3975
dc.identifier.urihttp://hdl.handle.net/123456789/65
dc.language.isoenen_US
dc.subjectmassively parallel computingen_US
dc.subjectinterval-valued computingen_US
dc.titleInterval-valued computations and their connection to PSPACEen_US
dc.title.journalTheoretical Computer Scienceen_US
dc.type.classArticleen_US
dc.type.specificationScientificen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
tcs-revised-submitted.pdf
Size:
423.61 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.57 KB
Format:
Item-specific license agreed upon to submission
Description: