Solving a PSPACE-problem by a linear interval-valued computation

dc.contributor.authorVályi, Sándor
dc.contributor.authorNagy, Benedek
dc.contributor.bookeditorBeckmann, Arnold
dc.contributor.bookeditorBerger, Ulrich
dc.contributor.bookeditorLöwe, Benedikt
dc.contributor.bookeditorTucker, John V.
dc.date.accessioned2012-06-14T12:36:13Z
dc.date.available2012-06-14T12:36:13Z
dc.date.conferenceend2006-07-05
dc.date.conferencestart2006-06-30
dc.date.issued2012-06-14
dc.date.year2006
dc.description.abstractWe continue investigation of interval-valued computing based on \cite{NB1} where computation is executed on interval-valued bytes which are bits indexed by the interval [0,1] rather than by a finite set. This device was presented there as a new possible model of analogue computers. Also the question was posed in \cite{NB1}, which complexity is needed to solve PSPACE-complete problems in this paradigm. We answer this question. Namely, we show that the problem of validity of quantified propositional formulae is decidable by a linear interval-valued computation.en_US
dc.description.citySwanseaen_US
dc.description.conferencetypeInternationalen_US
dc.description.countryGreat Britainen_US
dc.format.firstpage216en_US
dc.format.lastpage225en_US
dc.format.pages10en_US
dc.identifier.isbn0-86076-189-4en_US
dc.identifier.urihttp://hdl.handle.net/123456789/63
dc.language.isoenen_US
dc.publisher.placeSwanseaen_US
dc.publisher.publisherUniversity of Wales Swanseaen_US
dc.subjectmassively parallel computingen_US
dc.subjectinterval-valued computingen_US
dc.titleSolving a PSPACE-problem by a linear interval-valued computationen_US
dc.title.bookLogical Approaches to Computational Barriersen_US
dc.title.booksubtitleReport # CSR 7-2006en_US
dc.title.conferenceSecond Conference on Computability in Europe, 2006en_US
dc.type.classPaper of lecture or posteren_US
dc.type.specificationScientificen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
qsat.pdf
Size:
254.48 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: