Loading...
Please wait, while we are loading the content...
Similar Documents
Interval-valued computations and its connection with PSPACE
| Content Provider | Semantic Scholar |
|---|---|
| Author | Nagy, Benedek Vályi, Sándor |
| Copyright Year | 2007 |
| Abstract | At the conference CiE2005, B. Nagy 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://dea.lib.unideb.hu/dea/bitstream/handle/2437/81988/postfile_up_tcs-revisedOK.pdf?isAllowed=y&sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
