Interval-valued computations without the product operator. (English)
Kovács, Emőd (ed.) et al., Proceedings of the 7th international conference on applied informatics (ICAI 2007), January 28‒31, 2007, Eger, Hungary. Vol. I. Eger: Eszterházy Károly College. 81-88 (2009).
In [An interval-valued computing device, in: Computability in Europe 2005: New Computational Paradigms, ILLC Publications X-2005-01, Amsterdam, 166‒177 (2005)], the first author 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 [Interval-valued computations: introduction and connection to classical complexity theory, Theor. Comput. Sci., accepted for publication], the authors 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 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.