The Experts below are selected from a list of 42306 Experts worldwide ranked by ideXlab platform
Leon O. Chua - One of the best experts on this subject based on the ideXlab platform.
-
THE CNN Universal Machine: 10 YEARS LATER
Journal of Circuits Systems and Computers, 2003Co-Authors: Tamas Roska, Leon O. ChuaAbstract:In 1992, a new spatial temporal computing idea had been proposed, the CNN Universal Machine. It turned out that a new paradigm in computing on image flows, a Universal Machine on Flows, has ignited the intellect of hundreds of researchers. Today, visual microprocessors based on this idea can perform about TeraOPS computing power and 10 000 frames per second. In this paper, after a brief description of the history of the invention, architectural advances, physical implementation, algorithmic developments, as well as the biology relevance, theoretical aspects, mission critical applications, and new directions are reviewed.
-
Very low bit‐rate video coding using cellular neural network Universal Machine
International Journal of Circuit Theory and Applications, 1999Co-Authors: Krzysztof Slot, Leon O. Chua, Tamas RoskaAbstract:A method of video coding for very low bit-rate channels, which is implemented using cellular neural network Universal Machine, is presented in the following paper. The presented method combines elements of a standard approach to video coding with elements of second-generation video-coding techniques. Inter-frame coding is performed using standard block-based motion estimation procedure, while intra-frame coding is based on vector quantization approach. To satisfy constraints imposed by very low bit-rate channel throughput, a number of bytes that were considered to be used for representing video sequence frames, was assumed to be less than 200. Simulations of the algorithm execution, based on actual CNN UM chip parameter values, show feasibility of using the proposed method for real-time implementation of very low bit-rate video coding.
-
Implementation of arbitrary Boolean functions on a CNN Universal Machine
International Journal of Circuit Theory and Applications, 1998Co-Authors: L. Nemes, Leon O. Chua, Tamas RoskaAbstract:The demand for implementing arbitrary N-variable logic functions on perceptron-like structures arises quite often in practice. It is well known, that only the linearly separable class of Boolean functions can be implemented in a single step on these structures. This class however, constitutes only a small (and with the increasing N exponentially decreasing) part of all logic functions. All Boolean functions can be trivially decomposed into at most 2N−1 sub-functions by implementing the minterm or maxterm formulation of the function. This approach, however, becomes rather impractical with the increasing number of variables. In this paper an algorithm is proposed for decomposing arbitrary, linearly non-separable Boolean functions into a series of separable functions, which can be then efficiently implemented as a program for the CNN Universal Machine assuming the simplest and most robust hardware architecture. The decomposition is achieved by finding the closest linearly separable compact functions. Robustness issues of the implementation are also addressed. © 1998 John Wiley & Sons, Ltd.
-
object oriented image analysis for very low bitrate video coding systems using the cnn Universal Machine
International Journal of Circuit Theory and Applications, 1997Co-Authors: Alexander Stoffels, Tamas Roska, Leon O. ChuaAbstract:The CNN Universal Machine (CNNUM) is applied to object-oriented video compression and proves its Universality for future applications in the field of very-low-bitrate coding. This proposal joins recent work of Venetianer and Roska in unfolding the enormous computational abilities of the CNNUM for a wide class of video compression techniques. Here a novel image analysis technique is considered and realized in the form of analogic CNN algorithms. The specific features of the scheme, among them the extensive use of dynamic (finite running time) CNN cloning templates, are outlined and discussed through different computer simulations. When implemented on the CNNUM, its performances outdo those of equivalent digital systems and qualify the CNNUM as a serious competitor for future video coding hardware. © 1997 John Wiley & Sons, Ltd.
-
Efficient implementation of neighborhood logic for cellular automata via the Cellular Neural Network Universal Machine
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 1997Co-Authors: K.r. Crounse, E.l. Fung, Leon O. ChuaAbstract:The main difficulty in implementing cellular automata on the Cellular Neural Network Universal Machine (CNNUM) is the need to perform arbitrary logic functions of the input neighborhood. Since the architecture computes weighted sums of this neighborhood, by using a "B-template," it is limited to threshold logic, i.e., a logical operation to be computed by a single transient must be in the class of linearly separable Boolean functions. It was shown previously how a general logic function can be implemented on the CNNUM by cascading component functions from this class-namely by the direct implementation of the minterm or maxterm formulation of the desired function. However, for functions of a 3/spl times/3 input neighborhood this method may require up to 256 stages. We propose a more efficient method for implementing general logic functions on the CNNUM and other hardwares capable of performing a threshold logic function of an input neighborhood. The class of considered component functions is a superset of the minterms and maxterms but, for purposes of searchability, ease of implementation, and robustness, a subset of the general linearly separable Boolean functions. We have formulated an algorithm that will find a sequence of weight-restricted threshold logic functions (B-templates with weights from {-1, 0, +1} and a bias) that, when cascaded together using two-input logical operations, will result in the desired Boolean function. Two examples are given to exhibit the algorithm.
Michal Koucký - One of the best experts on this subject based on the ideXlab platform.
-
What can be efficiently reduced to the Kolmogorov-random strings?
Annals of Pure and Applied Logic, 2006Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:Abstract We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R C . This question arises because PSPACE ⊆ P R C and NEXP ⊆ NP R C , and no larger complexity classes are known to be reducible to R C in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. What follows is a list of some of our main results. • Although Kummer showed that, for every Universal Machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to R C U in time t , there is no such time bound t that suffices for every Universal Machine U . We also show that, for some Machines U , the disjunctive reduction can be computed in as little as doubly-exponential time. • Although for every Universal Machine U , there are very complex sets that are ≤ dtt P -reducible to R C U , it is nonetheless true that P = REC ∩ ⋂ U { A : A ≤ dtt P R C U } . (A similar statement holds for parity-truth-table reductions.) • Any decidable set that is polynomial-time monotone-truth-table reducible to R C is in P / poly . • Any decidable set that is polynomial-time truth-table reducible to R C via a reduction that asks at most f ( n ) queries on inputs of size n lies in P / ( f ( n ) 2 f ( n ) 3 log f ( n ) ) .
-
STACS - What Can be Efficiently Reduced to the K-Random Strings?
Lecture Notes in Computer Science, 2004Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R K . We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. Among other results, we show that although for every Universal Machine U, there are very complex sets that are \(\leq^{p}_{dtt}\)-reducible to R k ∪ , it is nonetheless true that P=REC \(\cap\bigcap\cup\{A:A\leq^{p}_{dtt} R_{k\cup}\}\). We also show for a broad class of reductions that the sets reducible to R K have small circuit complexity.
-
What can be efficiently reduced to the K-random strings?
Lecture Notes in Computer Science, 2004Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R K . We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. Among other results, we show that although for every Universal Machine U, there are very complex sets that are ≤ p dtt-reducible to R KU , it is nonetheless true that P = REC ∩ ∩ U {A: A ≤ p dtt R KU }. We also show for a broad class of reductions that the sets reducible to R K have small circuit complexity.
Tamas Roska - One of the best experts on this subject based on the ideXlab platform.
-
Perspectives for Monte Carlo simulations on the CNN Universal Machine
International Journal of Modern Physics C, 2006Co-Authors: Mária Ercsey-ravasz, Tamas Roska, Zoltán NédaAbstract:Possibilities for performing stochastic simulations on the analog and fully parallelized Cellular Neural Network UniversalMachine (CNN-UM) are investigated. By using a chaotic cellular automaton perturbed with the natural noise of the CNN-UM chip, a realistic binary random number generator is built. As a specific example for Monte Carlo type simulations, we use this random number generator and a CNN template to study the classical site-percolation problem on the ACE16K chip. The study reveals that the analog and parallel architecture of the CNN-UM is very appropriate for stochastic simulations on lattice models. The natural trend for increasing the number of cells and local memories on the CNN-UM chip will definitely favor in the near future the CNN-UM architecture for such problems.
-
THE CNN Universal Machine: 10 YEARS LATER
Journal of Circuits Systems and Computers, 2003Co-Authors: Tamas Roska, Leon O. ChuaAbstract:In 1992, a new spatial temporal computing idea had been proposed, the CNN Universal Machine. It turned out that a new paradigm in computing on image flows, a Universal Machine on Flows, has ignited the intellect of hundreds of researchers. Today, visual microprocessors based on this idea can perform about TeraOPS computing power and 10 000 frames per second. In this paper, after a brief description of the history of the invention, architectural advances, physical implementation, algorithmic developments, as well as the biology relevance, theoretical aspects, mission critical applications, and new directions are reviewed.
-
COMPUTATIONAL AND COMPUTER COMPLEXITY OF ANALOGIC CELLULAR WAVE COMPUTERS
Journal of Circuits Systems and Computers, 2003Co-Authors: Tamas RoskaAbstract:The CNN Universal Machine is generalized as the latest step in computational architectures: a Universal Machine on Flows. Computational complexity and computer complexity issues are studied in different architectural settings. Three mathematical Machines are considered: the Universal Machine on integers (UMZ), the Universal Machine on reals (UMR) and the Universal Machine on flows (UMF). The three Machines induce different kinds of computational difficulties: combinatorial, algebraic, and dynamic, respectively. After a broader overview on computational complexity issues, it is shown, following the reasoning related the UMR, that in many cases the size is not the most important parameter related to computational complexity. Emerging new computing and computer architectures as well as their physical implementation suggest a new look on computational and computer complexities. The new analog-and-logic (analogic) cellular array computer paradigm, based on the CNN Universal Machine, and its physical implementation in CMOS and optical technologies, proves experimentally the relevance of the role of accuracy and problem parameter in computational complexity. We introduce also the rigorous definition of computational complexity for UMF and prove an NP class of problems. It is also shown that choosing the spatial temporal elementary instructions, as well as taking into account the area and power dissipation, these choices inherently influence computational complexity and computer complexity, respectively. Comments related to relevance to biology of the UMF are presented in relation to complexity theory. It is shown that algorithms using spatial-temporal continuous elementary instructions (α-recursive functions) represent not only a new world in computing, but also, a more general type of logic inference.
-
Gradient Computation of Continuous-Time Cellular Neural/Nonlinear Networks with Linear Templates via the CNN Universal Machine
Neural Processing Letters, 2002Co-Authors: Mátyás Brendel, Tamas Roska, Gusztáv BártfaiAbstract:Single-layer, continuous-time cellular neural/nonlinear networks (CNN) are considered with linear templates. The networks are programmed by the template-parameters. A fundamental question in template training or adaptation is the gradient computation or approximation of the error as a function of the template parameters. Exact equations are developed for computing the gradients. These equations are similar to the CNN network equations, i.e. they have the same neighborhood and connectivity as the original CNN network. It is shown that a CNN network, with a modified output function, can compute the gradients. Thus, fast on-line gradient computation is possible via the CNN Universal Machine, which allows on-line adaptation and training. The method for computing the gradient on-chip is investigated and demonstrated.
-
Adaptive image sensing and enhancement using the cellular neural network Universal Machine: Research Articles
International Journal of Circuit Theory and Applications, 2002Co-Authors: Mátyás Brendel, Tamas RoskaAbstract:As an attempt to introduce interactive, content-dependent adaptive (ICDA) image processing, a simple but powerful active image sensing and two image enhancement methods are introduced via adaptive CNN-UM sensor-computers. Thus, the method ICDA can be used for adaptive control of image sensing and for subsequent on-line or off-line image enhancement as well. The algorithms use both intensity and contrast content. The image sensing technology can be realized with the current CNN-UM chip. Our first image enhancement method is also executable on this chip, but it is more suitable for the adaptive cellular neural network Universal Machine (ACNN-UM) architecture. Some results of simulator and chip experiments and an adaptive extended cell are presented. Our second, dynamical image enhancement method is planned to be executable on a multi-layer, complex cell CNN architecture. In (Proceedings of the 6th IEEE International Workshop on Cellular Neural Networks and their Applications (CNNA-2000) Catania, 2000; 213–217) 3-layer architecture is described which is capable of realizing the main part of the second enhancement method.The main issues of our paper are as follows: the novel outlook of the ICDA framework, three new methods for two key application areas of CNN-UM, the notion of ‘regional’ adaptive computing, the novelty of application of equilibrium-computing in the third method. However, the key novelty of our work is not just a new method and a new realization: by combining sensing and computing, dynamically and pixelwise, a new quality becomes practical. Copyright © 2002 John Wiley & Sons, Ltd.
Eric Allender - One of the best experts on this subject based on the ideXlab platform.
-
What can be efficiently reduced to the Kolmogorov-random strings?
Annals of Pure and Applied Logic, 2006Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:Abstract We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R C . This question arises because PSPACE ⊆ P R C and NEXP ⊆ NP R C , and no larger complexity classes are known to be reducible to R C in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. What follows is a list of some of our main results. • Although Kummer showed that, for every Universal Machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to R C U in time t , there is no such time bound t that suffices for every Universal Machine U . We also show that, for some Machines U , the disjunctive reduction can be computed in as little as doubly-exponential time. • Although for every Universal Machine U , there are very complex sets that are ≤ dtt P -reducible to R C U , it is nonetheless true that P = REC ∩ ⋂ U { A : A ≤ dtt P R C U } . (A similar statement holds for parity-truth-table reductions.) • Any decidable set that is polynomial-time monotone-truth-table reducible to R C is in P / poly . • Any decidable set that is polynomial-time truth-table reducible to R C via a reduction that asks at most f ( n ) queries on inputs of size n lies in P / ( f ( n ) 2 f ( n ) 3 log f ( n ) ) .
-
STACS - What Can be Efficiently Reduced to the K-Random Strings?
Lecture Notes in Computer Science, 2004Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R K . We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. Among other results, we show that although for every Universal Machine U, there are very complex sets that are \(\leq^{p}_{dtt}\)-reducible to R k ∪ , it is nonetheless true that P=REC \(\cap\bigcap\cup\{A:A\leq^{p}_{dtt} R_{k\cup}\}\). We also show for a broad class of reductions that the sets reducible to R K have small circuit complexity.
-
What can be efficiently reduced to the K-random strings?
Lecture Notes in Computer Science, 2004Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R K . We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. Among other results, we show that although for every Universal Machine U, there are very complex sets that are ≤ p dtt-reducible to R KU , it is nonetheless true that P = REC ∩ ∩ U {A: A ≤ p dtt R KU }. We also show for a broad class of reductions that the sets reducible to R K have small circuit complexity.
Harry Buhrman - One of the best experts on this subject based on the ideXlab platform.
-
What can be efficiently reduced to the Kolmogorov-random strings?
Annals of Pure and Applied Logic, 2006Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:Abstract We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R C . This question arises because PSPACE ⊆ P R C and NEXP ⊆ NP R C , and no larger complexity classes are known to be reducible to R C in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. What follows is a list of some of our main results. • Although Kummer showed that, for every Universal Machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to R C U in time t , there is no such time bound t that suffices for every Universal Machine U . We also show that, for some Machines U , the disjunctive reduction can be computed in as little as doubly-exponential time. • Although for every Universal Machine U , there are very complex sets that are ≤ dtt P -reducible to R C U , it is nonetheless true that P = REC ∩ ⋂ U { A : A ≤ dtt P R C U } . (A similar statement holds for parity-truth-table reductions.) • Any decidable set that is polynomial-time monotone-truth-table reducible to R C is in P / poly . • Any decidable set that is polynomial-time truth-table reducible to R C via a reduction that asks at most f ( n ) queries on inputs of size n lies in P / ( f ( n ) 2 f ( n ) 3 log f ( n ) ) .
-
STACS - What Can be Efficiently Reduced to the K-Random Strings?
Lecture Notes in Computer Science, 2004Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R K . We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. Among other results, we show that although for every Universal Machine U, there are very complex sets that are \(\leq^{p}_{dtt}\)-reducible to R k ∪ , it is nonetheless true that P=REC \(\cap\bigcap\cup\{A:A\leq^{p}_{dtt} R_{k\cup}\}\). We also show for a broad class of reductions that the sets reducible to R K have small circuit complexity.
-
What can be efficiently reduced to the K-random strings?
Lecture Notes in Computer Science, 2004Co-Authors: Eric Allender, Harry Buhrman, Michal KouckýAbstract:We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R K . We show that this question cannot be posed without explicitly dealing with issues raised by the choice of Universal Machine in the definition of Kolmogorov complexity. Among other results, we show that although for every Universal Machine U, there are very complex sets that are ≤ p dtt-reducible to R KU , it is nonetheless true that P = REC ∩ ∩ U {A: A ≤ p dtt R KU }. We also show for a broad class of reductions that the sets reducible to R K have small circuit complexity.
