This paper investigates prefix computations on Iterative Arrays (IAs) with sequential input/output mode. We show that, for any language L accepted by a linear-time IA, there is an IA which, given an infinite string a1a2 ai, generates the values of χL(a1),χL(a1a2),,χL(a1a2 ai), at steps 4,16,,4i2,, respectively. Here, χL:Σ*{0,1} is the characteristic function of the language L Σ*, defined as χL(w) = 1 iff w L. We also construct 2i3-time and i4-time prefix algorithms for languages accepted by quadratic-time and cubic-time IAs, respectively.

Interval arithmetic is able to be applied when we include the ranges of various functions. When we include them applying the interval arithmetic, the serious problem that the widths of the range inclusions increase extremely exists. In range inclusion of polynomials particularly, Horner's method and Alefeld's method are well known as the conventional methods which mitigates this problem. The purpose of this paper is to propose the new methods which are able to mitigate this problem more efficiently than the conventional methods. And in this paper, we show and compare the efficiencies of the new methods by some numerical examples.

A new algorithm and architecture to eliminate redundant operations in block-matching (BM) motion estimation is proposed. The key step of this work is to use binary-matching to define image regions with the static background content and then exclude these regions from the actual motion estimation. According to experiments, the approach maintains the highest PSNR, while making as half as less computations in comparison to the adaptive BM or 1/8 of the computations required by the full-search BM. An implementation scheme is outlined.

The safety problem in access matrix models determines whether a given subject can eventually obtain access privilege to a given object. Generally speaking, the safety problem is, unfortunately undecidable. Not much is known about protection systems for which the safety problem is decidable, except for strongly constrained systems (e.g., monotonic systems). Therefore, we propose the Dynamic-Typed Access Matrix (DTAM) Model, which extends the Typed Access Matrix model of Sandhu by allowing the type of an object to change dynamically. The DTAM model has an advantage that it can describe non-monotonic protection systems for which the safety problem is decidable. In particular, with further restrictions, we can show that the problem becomes NP-hard. In this paper, we formally define the DTAM model and then discuss various aspects of it thoroughly.

A novel method is presented to compute moments of high-speed VLSI interconnects, which are modeled as coupled RLC trees. Recursive formulae of moments of coupled RC trees are extended to those for coupled RLC trees by considering both self inductances and mutual inductances. Analytical formulae for voltage moments at each node are derived explicitly. The formulae can be efficiently used for estimating delay and crosstalk noise. The inductive crosstalk noise waveform can be accurately and efficiently estimated using the moment computation technique in conjunction with the projection-based order reduction method. Fundamental aspects of the proposed approach are described in details. Experimental results show the increased accuracy of the proposed method over that of the traditional ones.

Genetic algorithm (GA) is a widely used numerical technique to simplify some analytical solutions in electromagnetic theory. Genetic algorithms can be combined with the geometric optics method to tackle electromagnetic scattering problems. This paper presents an extrapolation procedure, which derived, as a first step, a functional representation of the radar cross section (RCS) of three different dielectric objects that was computed via the Mie solution or the method of moments (MOM). An algorithm was employed to fit the scattering characteristics of dielectric objects at high frequencies.

Finding a nonnegative integer solution x for Ax = b (A Zmn, b Zm1) in Petri nets is NP-complete. Being NP-complete, even algorithms with theoretically bad worst case and with average complexity can be useful for a special class of problems, hence deserve investigation. Then a Grobner basis approach to integer programming problems was proposed in 1991 and some symbolic computation systems became to have useful tools for ideals, varieties, and algorithms for algebraic geometry. In this letter, Grobner basis approach is applied to three typical problems with respect to state equation in P/T Petri nets. In other words, after Grobner bases are derived by the tool Maple 7, we consider how to derive the T-invariants and particular solutions of the Petri nets by using them in this letter.

The imprecise computation model is one of the flexible computation models used to construct real-time systems. It is especially useful when the worst case execution times are difficult to estimate or the execution times vary widely. Although there are several ways to implement this model, they have not attained much attentions of real-world application programmers to date due to their unrealistic assumptions and high dependency on the execution environment. In this paper, we present an integrated approach for implementing the imprecise computation model. In particular, our research covers three aspects. First, we present a new imprecise computation model which consists of a mandatory part, an optional part, and another mandatory part called wind-up part. This wind-up part allows application programmers to explicitly incorporate into their programs the exact operations needed for safe degradation of performance when there is a shortage in resources. Second, we describe a scheduling algorithm called Mandatory-First with Wind-up Part (M-FWP) which is based on the Earliest Deadline First strategy. This algorithm, unlike scheduling algorithms developed for the classical imprecise computation model, is capable of scheduling a mandatory portion after an optional portion. Third, we present a dynamic priority server method for an efficient implementation of the M-FWP algorithm. We also show that the number of the proposed server at most needed per node is one. In order to estimate the performance of the proposed approach, we have implemented a real-time operating system called RT-Frontier. The experimental analyses have proven its ability to implement tasks based on the imprecise computation model without requiring any knowledge on the execution time of the optional part. Moreover, it also showed performance gain over the traditional checkpointing technique.

Affine arithmetic is a kind of interval arithmetic defined by Stolfi et al. In affine arithmetic, it is difficult to realize the efficient nonlinear binomial operations. The purpose of this letter is to propose a new dividing method which is able to supply more suitable evaluation than the old dividing method. And this letter also shows the efficiency of the new dividing method by numerical examples.

This paper examines the descriptive power and the limitations of a simple reinforcement learning model (REL), comparing the simulation results with the results of an economic experiment employing human subjects. Agent-based computational economics and experimental economics are becoming increasingly popular as tools for economists. A new variety of learning model using games with a unique equilibrium is proposed and examined in both of the fields mentioned above. However, little attention is given to games with multiple equilibria. We examine threshold public goods games with two types of equilibria, where each player in a five-person group simultaneously contributes the public goods from her private endowments. In the experiments, we observe two patterns of the subjects' behavior: the cooperative and non-cooperative patterns. Our simulation results show that the REL reproduces the cooperative pattern, but does not reproduce the non-cooperative pattern. However, the results suggest that the REL does reproduce the non-cooperative pattern in terms of the agents' internal states. That implies that deterministic strategies would be required to reproduce the non-cooperative pattern in the games. We show an example of the REL with deterministic strategies.

A new beamforming method based on simplex downhill optimaization process has been presented for the reverse link CDMA systems. The proposed system performs code-filtering at each antenna for each user. The new beamforming method gives lower computations and faster convergence properties than existing algorithms. The simulation results show that the proposed algorithm has a better BER performance in the case of the time-varing channel.

The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.

We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al. 's amplitude amplification method, and analogous to Buhrman et al. 's algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.

The main contribution of this paper is to present an image retrieval system using FPGAs. Given a template image T and a database of a number of images I1, I2,, our system lists all images that contain a subimage similar to T. More specifically, a hardware generator in our system creates the Verilog HDL source of a hardware that determines whether Ii has a similar subimage to T for any image Ii and a particular template T. The created Verilog HDL source is compiled and embedded in an FPGA using the design tool provided by the FPGA vendor. Since the hardware embedded in the FPGA is designed for a particular template T, it is an instance-specific hardware that allows us to achieve extreme acceleration. We evaluate the performance of our image matching hardware using a PCI-connected Xilinx FPGA and a timing analyzer. Since the generated hardware attains up to 3000 speed-up factor over the software solution, our approach is promising.

The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of and a solution s to it, find a solution to x other than s. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.

The label placement problem is one of the most important problems in geographic information systems, cartography, graph drawing and graphical interface design. In this paper, we consider the problem of labeling points and curves in maps drawn from digital data. In digital maps, a curve is represented as a set of points and consists of many small segments. The label for each curve must be placed alongside the corresponding curve. We define a continuous labeling space for points and curves, and present an algorithm using this space for positioning labels. Computational results for subway and JR train maps in Tokyo are presented.

This paper concerns recognizing 3-dimensional object using proposed multi-layer block model. In particular, we aim to achieve desirable recognition performance while restricting the computational load to a low level using 3-step feature extraction procedure. An input image is first precisely partitioned into hierarchical layers of blocks in the form of base blocks and overlapping blocks. The hierarchical blocks are merged into a matrix, with which abundant local feature information can be obtained. The local features extracted are then employed by the kernel based support vector machines in tournament for enhanced system recognition performance while keeping it to low dimensional feature space. The simulation results show that the proposed feature extraction method reduces the computational load by over 80% and preserves the stable recognition rate from varying illumination and noise conditions.

In the last three decades of the 20th Century, research in speech recognition has been intensively carried out worldwide, spurred on by advances in signal processing, algorithms, architectures, and hardware. Recognition systems have been developed for a wide variety of applications, ranging from small vocabulary keyword recognition over dial-up telephone lines, to medium size vocabulary voice interactive command and control systems for business automation, to large vocabulary speech dictation, spontaneous speech understanding, and limited-domain speech translation. Although we have witnessed many new technological promises, we have also encountered a number of practical limitations that hinder a widespread deployment of applications and services. On one hand, fast progress was observed in statistical speech and language modeling. On the other hand only spotty successes have been reported in applying knowledge sources in acoustics, speech and language science to improving speech recognition performance and robustness to adverse conditions. In this paper we review some key advances in several areas of speech recognition. A bottom-up detection framework is also proposed to facilitate worldwide research collaboration for incorporating technology advances in both statistical modeling and knowledge integration into going beyond the current speech recognition limitations and benefiting the society in the 21st century.

In this paper, parallelization methods for quantum circuits are studied, where parallelization of quantum circuits means to reconstruct a given quantum circuit to one which realizes the same quantum computation with a smaller depth, and it is based on using additional bits, called ancillae, each of which is initialized to be in a certain state. We propose parallelization methods in terms of the number of available ancillae, for three types of quantum circuits. The proposed parallelization methods are more general than previous one in the sense that the methods are applicable when the number of available ancillae is fixed arbitrarily. As consequences, for the three types of n-bit quantum circuits, we show new upper bounds of the number of ancillae for parallelizing to logarithmic depth, which are 1/log n of previous upper bounds.

We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.