The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension matrices with integer or rational entries is studied. We call these two problems and , respectively, for short. We prove that: (i) For , does not belong to , unless .newline (ii) For stochastic matrices : belongs to while, for , does not belong to , unless . (iii) For any k, belongs to .
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
The exchange of preprints and journals plays an important role to communicate new research ideas and results in many academic fields. Distribution of preprints and journal articles by electronic file via the Internet has become a primary method in addition to paper publication. Electronic preprints and articles in the paperless era should be certified in terms of existence proof and tamper resistance because they are easily modified by their site administrator. We developed a secure preprint and...
The effective scheduling of operations in batch plants has a great potential for high economic returns, in which the formulation and an optimal solution algorithm are the main issues of study. Petri nets have proven to be a promising technique for solving many difficult problems associated with the modelling, formal analysis, design and coordination control of discrete-event systems. One of the major advantages of using a Petri-net model is that the same model can be used for the analysis of behavioural...
We study a time-delay regularization of the anisotropic diffusion model for image denoising of Perona and Malik [IEEE Trans. Pattern Anal. Mach. Intell 12 (1990) 629–639], which has been proposed by Nitzberg and Shiota [IEEE Trans. Pattern Anal. Mach. Intell 14 (1998) 826–835]. In the two-dimensional case, we show the convergence of a numerical approximation and the existence of a weak solution. Finally, we show some experiments on images.
We study a time-delay regularization of the anisotropic diffusion model for image denoising of Perona and Malik [IEEE Trans. Pattern Anal. Mach. Intell12 (1990) 629–639], which has been proposed by Nitzberg and Shiota [IEEE Trans. Pattern Anal. Mach. Intell14 (1998) 826–835]. In the two-dimensional case, we show the convergence of a numerical approximation and the existence of a weak solution. Finally, we show some experiments on images.
Simple Temporal Networks (STN) allow conjunctions of minimum and maximum distance constraints between pairs of temporal positions to be represented. This paper introduces an extension of STN called Time–dependent STN (TSTN), which covers temporal constraints for which the minimum and maximum distances required between two temporal positions x and y are not necessarily constant but may depend on the assignments of x and y. Such constraints are useful to model problems in which the duration of an...