Interval-valued computations without the product operator

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.