In this paper we propose a comprehensive approach to physical design based on the constraint paradigm. Bounds on the most critical circuit parasitics are automatically generated to help designers and/or physical design tools meet a set of high-level specifications. The constraint generation engine is based on constrained optimization, where various parasitic effects on interconnect and devices are accounted for and dealt with in different manners according to their statistical behavior and their effect on performance.

In this paper, we propose a new strategy of estimating correlation dimensions in combination with the method of surrogate data, which is a kind of statistical control usually introduced to avoid spurious estimates of nonlinear statistics, such as fractal dimensions, Lyapunov exponents and so on. In the case of analyzing time series with the method of surrogate data, it is desirable to decide values of estimated nonlinear statistics of the original data and surrogate data sets as exactly as possible. However, when dimensional analysis is applied to possible attractors reconstructed from real time series, it is very dangerous to decide a single value as the estimated dimensions and desirable to analyze its scaling property for avoiding spurious estimates. In order to solve this defficulty, a dimension estimator algorithm and the method of surrogate data are combined by introducing Monte Carlo hypothesis testing. In order to show effectiveness of the new strategy, firstly artificial time series are analyzed, such as the Henon map with additive noise, filtered random numbers and filtered random numbers transformed by a static monotonic nonlinearity, and then experimental time series are also examined, such as wolfer's sunspot numbers and the fluctuations in a farinfrared laser data.

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Hence the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (witness) that disproves the inclusion for a pair of real-time droca's which accept by final state, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts by empty stack, it is called strict. A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by strict droca's is a subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Hence the decidablity of the equivalence problem for strict droca's is obvious. In this paper, we present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by strict droca's. Then we show that the worst-case time complexity of our algorithm is polynomial with respect to these automata.

Over the last decade, research in the automatic synthesis and optimization of combinational logic has matured significantly; more recently, research has focused on sequential logic. Many of the paradigms for combinational logic have been extended and applied in the sequential domain. In addition, promising new directions for future research are being explored. In this paper, we survey some of the results of combinational synthesis and some recent results for sequential synthesis and then use these to view possible avenues for future sequential synthesis research. In particular we look at two related questions: deriving a set of permissible behaviors and using a minimizer to select the best behavior according to some optimization criteria. We examine these two issues in increasingly complex situations starting with a single-output function, and proceeding to a single multiple-output function, a network of single-output functions, a network of multiple-output functions, and then similar questions where function" is replaced by a finite state machine (FSM). We end with a discussion of a network of finite state machines and the problem of deriving the set of permissible FSM's and choosing a representative minimum one.

In improving channel utilization in microcellular systems, adaptive channel allocation using distributed control has been reported to be effective. We describe an analytical approximation algorithm for channel dimensioning of distributed adaptive channel allocation. We compare our analytical results with simulation results and show the characteristics of permissible load as a function of the number of base station channels based on our method. Finally we illustrate traffic design and administration based on our algorithm.

This paper describes that a neural network, which consists of neurons with piecewise–linear sigmoid characteristics, is able to approximate any piecewise–linear map with origin symmetry. The neural network can generate "deterministic diffusion" originating from its diffusive trajectory.

It is of significantly importance in relation to the problem of diagnosis of deviation faults in linear analog circuits to check whether or not it is possible to uniquely determine the element-values in a given linear analog circuit from the node-voltage measurements at its accessible nodes and then of giving a method for actual computation of the element-values if it is possible, under the assumption that i) the circuit is of known topology (and of known element-kinds if possible) and ii) the actual value of each element-value of the circuit almost always deviates from the design value and is not known exactly. In this paper, the problem of checking the unique determinability of the element-values is called the element-value determinability problem, and its solutions which have been obtained until now are reviewed in perspectives to designing a publicly available user-oriented analog circuit diagnosis system.

This paper reviews two topics of nonlinear system analysis done in Japan. The first half of this paper concerns with nonlinear system analysis through the nondeterministic operator theory. The nondeterministic operator is a set-valued or fuzzy set valued operator by K. Horiuchi. From 1975 Horiuchi has developed fixed point theorems for nondeterministic operators. Using such fixed point theorems, he developed a unique theory for nonlinear system analysis. Horiuchi's theory provides a fundamental view point for analysis of fluctuations in nonlinear systems. In this paper, it is pointed out that Horiuchi's theory can be viewed as an extension of the interval analysis. Next, Urabe's theory for nonlinear boundary value problems is discussed. From 1965 Urabe has developed a method of computer assisted existence proof for solutions of nonlinear boundary value problems. Urabe has presented a convergence theorem for a certain simplified Newton method. Urabe's theorem is essentially based on Banach's contraction mapping theorem. In this paper, reformulation of Urabe's theory using the interval analysis is presented. It is shown that sharp error estimation can be obtained by this reformulation. Both works discussed in this paper have been done independently with the interval analysis. This paper points out that they have deep relationship with the interval analysis. Moreover, it is also pointed out that these two works suggest future directions of the interval analysis.

We are concerned with a subclass of deterministic pushdown automata (dpda) called very simple dpda's, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these dpda's. As usual, we take the maximal thickness (i.e., the length of the shortest input strings that make each stack symbol go to empry) of all stack symbols into account as one parameter of the given dpda's. Then the worst-case time complexity of our algorithm is polynomial with respect to these parameters. Without considering the thickness, the complexity is single exponential in the description length of the given dpda's. As far as we are concerned with very simple dpda's, our algorithm is very simple and direct, and is faster and much better than the previously given algorithms for the inclusion problem of dpda's.

The main result of this paper is an almost-everywhere hierarchy theorem for nondeterministic space that is as tight as the well-known infinitely-often hierarchy theorems for deterministic and nondeterministic space. In addition, we show that the complexity-theoretic notion of almost-everywhere complex functions is identical to the recursion-theoretic notion of bi-immune sets in the nondeterministic space domain. Finally, we investigate bi-immunity in nondeterministic and alternating time complexity classes and derive a similar hierarchy result for alternating time.

In the direct product space of a complete metric linear space X and its related space Y, a fuzzy mapping G is introduced as an operator by which we can define a projective fuzzy set G(x,y) for any xX and yY. An original system is represented by a completely continuous operator f(x)Y, e.g., in the form x=λ(f(x)), (λ is a linear operator), and a nondeterministic or fuzzy fluctuation induced into the original system is represented by a generalized form of system equation xβG(x,f(x)). By establishing a new fixed point theorem for the fuzzy mapping G, the existence and evaluation problems of solution are discussed for this generalized equation. The analysis developed here for the fluctuation problem goes beyond the scope of the perturbation theory.

An information retrieval system based on a dynamic thesaurus was developed utilizing the connectionist approach. The dynamic thesaurus consists of nodes, which represent each term of a thesaurus, and links, which represent the connections between nodes. Term information that is automatically extracted from user's relevant documents is used to change node weights and generate links. Thus, node weights and links reflect a user's interest. A document retrieval experiment using the dynamic thesaurus was conducted in which both a high recall rate and a high precision rate were achieved.