Interval-valued computations without the product operator
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In [1] B. Nagy introduced a new model for analog computations, namely
the interval-valued computations, where computation is executed on so-called
interval-valued bytes, which are special subsets of interval [0,1) rather than a
finite sequence of bits. The allowed set of computational operators on these
values were motivated by the operators usually applied to finite sequences
of bits, namely, Boolean operators and shifts, furthermore, a rather specific
kind of ”magnification“ operator, named there fractalian product.
In [4] S. Vályi and B. Nagy solved a PSPACE-complete problem by a
linear interval-valued computation. This solution depends on the possibility
of construction of interval-values with arbitrarily small components and
this step needs heavy application of products. In this article we show that
omitting this operator still results in a computational device with a high
computation power. Namely, we will demonstrate this by establishing that
the finite variable satisfaction problem of quantified propositional formulae is
still decidable by a fast (quadratic) interval-valued computation without any
application of the product operator.