Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: interval-valued computing

Sortuj według:

Ogranicz wyniki do:

Circular Interval-valued Computers and Simulation of (Red-green) Turing Machines

Nagy Benedek, Vályi Sándor

Fundamenta Informaticae

2021

Vol. 181, nr 2-3

213--238

Interval-valued computing is a kind of massively parallel computing. It operates on specific subsets of the interval [0,1) – unions of subintervals. They serve as basic data units and are called interval-values. It was established in [9], by a rather simple observation, that interval-valued computing, as a digital computing model, has computing power equivalent to Turing machines. However, this equivalence involves an unlimited number of interval-valued variables. In [14], the equivalence with Turing machines is established using a simulation that uses only a fixed number of interval-valued variables and this number depends only on the number of states of the Turing machine – in a logarithmic way. The simulation given there allows us to extend interval-valued computations into infinite length to capture the computing power of red-green Turing machines. In this extension of [14], based on the quasi-periodic techniques used in the simulations in that paper, a reformulation of the interval-valued computations is given, named circular interval-valued computers. This reformulation enforces the finiteness of the number of used interval-valued variables by building the finiteness into the syntax rules.

A Shift-free Characterization of NP within Interval-valued Computing

Nagy B., Vályi S.

Fundamenta Informaticae

2017

Vol. 155, nr 1/2

187--207

Interval-valued computing is a new computing paradigm that is based on manipulations of interval-values. Interval-values are finite unions of intervals on the unit interval [0; 1) so this kind of computing can be considered as a continuous space machine like optical computing [25]. Based on the massive parallelism of this paradigm, various intractable problems can be solved efficiently, i.e., by polynomial number of steps. In this paper, the well-known complexity classes, NP and coNP are addressed. A specific subclass of polynomial size interval-valued computations is proven to characterize NP, that is, exactly languages with non-deterministically polynomial time complexity can be decided by interval-valued computations of this subclass. This specific subclass of interval-valued computations does not use any of the shift operators, moreover the product operator is used only in the starting section of the computation. Due to the fact that interval-valued computing is a deterministic model of computing, an analogue result can be established for the class coNP.