This paper develops an algorithm based on the Modular Approach to solve singly constrained separable discrete optimization problems (Nonlinear Knapsack Problems). The Modular Approach uses fathoming and integration techniques repeatedly. The fathoming reduces the decision space of variables. The integration reduces the number of variables in the problem by combining several variables into one variable. Computational experiments for "hard" test problems with up to 1000 variables are provided. Each variable has up to 1000 integer values.

In order to investigate the dynamic behavior of quantized interconnection neural networks on neuro-chips, we have designed and fabricated hardware neural networks according to design rule of a 1.2 µm CMOS technology. To this end, we have developed programmable synaptic weights for the interconnection with three values of 1 and 0. We have tested the chip and verified the dynamic behavior of the networks in a circuit level. As a result of our study, we can provide the most straightforward application of networks for a dynamic pattern classifier. The proposed network is advantageous in that it does not need extra exemplar to classify shifted or reversed patterns.

In this paper, the bit error rate (BER) of 16 differential amplitude phase shift keying (16DAPSK) modems in future mobile communication system is derived analytically. The channel employed in this paper is the frequency-selective and fast Rayleigh fading channel, corrupted by cochannel interference (CCI) and additive white Gaussian noise (AWGN). Exact expressions for the probability distributions of the differential phase and amplitude ratio are derived for the BER calculation. The BER and optimum boundary are obtained for various channel conditions. In addition, the results for the BER in the presence of CCI are provided.

Recently, Garcia and Stichtenoth proposed sequences of algebraic function fields with finite constant fields such that their sequences attain the Drinfeld-Vl bound. In the sequences, the third algebraic function fields are Artin-Schreier extensions of Hermitian function fields. On the other hand, Miura presented powerful tools to construct one-point algebraic geometric (AG) codes from algebraic function fields. In this paper, we clarify rational functions of the third algebraic function fields which correspond to generators of semigroup of nongaps at a specific place of degree one. Consequently, we show generator matrices of the one-point AG codes with respect to the third algebraic function fields for any dimension by using rational functions of monomial type and rational points.

We discuss the security of the improved knapsack cryptosystem that Kobayashi and Kimura have proposed. Two attacking methods for their cryptosystem are proposed; one is the method for obtaining secret keys from public keys by using the continued fraction, and the other is for decrypting the ciphertext without knowing secret keys. We show that their cryptosystem is not secure against these attacks.

We here consider an extension of the validity of classical criteria ensuring the robustness of the statistical features of discrete time dynamical systems with respect to implementation inaccuracies and noise. The result is achieved by proving that, whenever a discrete time dynamical system is robust, all the discrete time dynamical systems topologically conjugate with it are also robust. In particular, this result offer an explanation for the stochastic robustness of the logistic map, which is confirmed by the reported experimental measurements.

Synchronization between two fully stretching piecewise affine Markov maps in the usual master-slave configuration has been proven to be possible in some interesting 2-dimensional and 3-dimensional cases. Aim of this contribution is to make a further step in the study of this phenomenon by showing that, if the two systems synchronize, the probability of having a certain synchronization time is bounded from above by an exponentially vanishing distribution. This result gives some formal ground to the numerical evidence shown in [2].

A formal necessary and sufficient condition on the general Petri net reachability problem is presented by eliminating all spurious solutions among known nonnegative integer solutions of state equation and unifying all the causes of those spurious solutions into a maximal-strongly-connected and siphon-and-trap subnet Nw. This result is based on the decomposition of a given net (N, Mo) with Md and the concepts of "no immature siphon at the reduced initial marking Mwo" and "no immature trap at the reduced end marking Mwd" on Nw which are both extended from "no token-free siphon at the initial marking Mo" and "no token-free trap at the end marking Md" on N, respectively, which have been both effectively, explicitly or implicitly, used in the well-known fundamental and simple subclasses.

VP Network Designer, a software tool that automates the tasks involved in the transaction of service orders in VP leased line services, is introduced here in this paper. The tool is composed of two functions: VP Design Explorer which, given a request for VP establishment, determines a disjoint backup and target VP routes to support fault tolerance under VP-APS scheme; Network Resource Administrator which provides data administering functions, useful in maintaining a clear insight into the state of the network. The paper focuses on the implementation of VP Design Explorer. A scheme, proposed as disjoint VP routes search, is used to evaluate a pair of VP routes that guarantee duct level independence. The scheme is based on an integer programming modeling approach, and is proved to be effective for evaluating disjoint paths in a hierarchical network. VP Design Explorer is equipped with an additional feature where, under conditions of resource shortage, it presents a set of additional resources that are necessary to satisfy VP demand, together with the VP routes that become possible by the additions. Formulation of the problem is attained through an extension of the disjoint VP routes search scheme. A prototype of VP Network Designer is presented and its performance tested using computer simulations. The tool is found to achieve a computational time performance in the order of seconds and minutes, for evaluating disjoint VP routes search problems under real life ATM network conditions.

This paper proposes implementation methods of fast ATM layer protection switching function. The main problem in attaining fast ATM protection is the number of connections in one transmission path. The transmission delay of the signal for protection negotiation procedure is relatively less than the processing time in the end nodes. Therefore shortening of the processing time in the nodes is a crucial factor for fast rerouting. This paper focuses on this point and presents some suitable implementations on ATM nodes for fast protection switching. These architectures can attain protection time of less than 50 ms after the detection of a failure at an end node. The key is load-sharing of the hardware and firmware. This paper also sums up the effectiveness of ATM protection and the current situation of standardization in ITU-T SG13.

In fully connected Multilayer perceptron (MLP), all the hidden units are activated by samples from the whole input space. For complex problems, due to interference and cross coupling of hidden units' activations, the network needs many hidden units to represent the problem and the error surface becomes highly non-linear. Searching for the minimum is then complex and computationally expensive, and simple gradient descent algorithms usually fail. We propose a network, where the input space is partitioned into local sub-regions. Subsequently, a number of smaller networks are simultaneously trained by overlapping subsets of the input samples. Remarkable improvement of training efficiency as well as generalization performance of this combined network are observed through various simulations.

Petri net is a graphical and mathematical tool for modelling, analysis, verification, and evaluation of discrete event systems. Liveness is one of the most important problems of Petri net analysis. This is concerned with a capability for firing of transitions and can be interpreted as a problem to decide whether the system under consideration is always able to reach a stationary behavior, or to decide whether the system is free from any redundant elements. An asymmetric choice (AC) net is a superclass of useful subclasses such as EFCs, FCs, SMs, and MGs, where SMs admit no synchronization, MGs admit no conflicts, FCs as well as EFCs admit no confusion, and ACs allow asymmetric confusion but disallow symmetric confusion. It is known that an AC net N is live iff it is place-live, but this is not the "initial-marking-based" condition and place-liveness is in general hard to test. For the initial-marking-based liveness for AC nets, it is only known that an AC net N is live if (but not only if) every deadlock in N contains a marked structural trap.

In this paper we present an algorithm to solve an as-yet untreated knapsack problem, the Multidimensional Multiple-choice Knapsack Problem (MMKP). Since our specific application occurs in the real-time domain, a solution for the MMKP with a small upper bound on the runtime is desirable. Thus, the Lagrange multiplier method is chosen, and a heuristic with a worst-case runtime behavior better than O(n2m) is developed, n being the number of elements and m the number of dimensions. Extensive testing against an exact algorithm based on partial enumeration is used to establish the accuracy and efficiency of the heuristic.

It is well known that the Hopfield Model (HM) for neural networks to solve the TSP suffers from three major drawbacks: (D1) it can converge to non-optimal local minimum solutions; (D2) it can also converge to non-feasible solutions; (D3) results are very sensitive to the careful tuning of its parameters. A number of methods have been proposed to overcome (D1) well. In contrast, work on (D2) and (D3) has not been sufficient; techniques have not been generalized to larger classes of optimization problems with constraint including the TSP. We first construct Extended HMs (E-HMs) that overcome both (D2) and (D3). The extension of the E-HM lies in the addition of a synapse dynamical system cooperated with the corrent HM unit dynamical system. It is this synapse dynamical system that makes the TSP constraint hold at any final states for whatever choices of the HM parameters and an initial state. We then generalize the E-HM further into a network that can solve a larger class of continuous optimization problems with a constraint equation where both of the objective function and the constraint function are non-negative and continuously differentiable.

Up to now, the only useful and well-known structural or initial-marking-based necessary and sufficient liveness conditions of Petri nets have only been those of an extended free-choice (EFC) net and its subclasses such as a free-choice (FC) net, a forward conflict free (FCF) net, a marked graph (MG), and a state machine (SM). All the above subclasses are activated only by deadlock-trap properties (i.e., real d-t properties in this paper), which mean that every minimal structural deadlock (MSDL ND=(SD, TD, FD, MoD)) in a net contains at least one live minimal structural trap (MSTR NT=(ST, TT, FT, MoT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), and the net with kindling traps NKT have recently been determined, in which each MSDL without real d-t properties was also activated by a new type of trap of trap, i.e., behavioral traps (BTRs), which are defined by introducing a virtual MSTR, a virtual maximal structural trap (virtual STR), a virtual MSDL, and a virtual maximal structural deadlock (virtual SDL) into a target MSDL. In this paper, a structural or initial-marking-based necessary and sufficient condition for local liveness (i.e., virtual deadlock-trap properties) of each MSDL ND s.t. SDST, SDST, SDST (but ND s.t. SDST is dead owing to real deadlock-trap properties) in a general Petri net N is presented by extending that in NKT. Specifically, live minimal behavioral traps (MBTRs) as well as live maximal behavioral traps (BTRs), i.e., virtual deadlock-trap properties, in a general Petri net N are characterized using the real d-t properties of each MSDL ND s.t. SDST for a general Petri net N, which were also obtained by extending the concept of return paths in NKT in connection with an MSDL which contains at least one MSTR and by using the concepts of T-cornucopias and absolute T-cornucopias in a subclass Ñ of N. In other words, BTRs are defined by introducing a virtual MSTR, a virtual STR, a virtual MSDL, and a virtual SDL into a target MSDL without real d-t properties. Additionally, a structural or initial-marking-based necessary and sufficient condition for liveness of a new subclass Nn of a general Petri net N (i.e., a general Petri net without time) is derived, and the usefulness of the obtained results is also discussed.

On a topographical map of civil engineering, there are various enclosed areas, for instance, rice fields, meadows, buildings, roads, walls, regional boundaries and so on. Before a software system such as road planer is run, it is necessary to extract these various regions and features, and to transform them to 3D data. The automatic extraction and classification of all of them on a screen are difficult and very time-consuming. It is better to combine the automatic recognition with interactive operation. It is obvious that interaction is easily done when vector date of maps is applied. On the other hand, the vector data is much less than the raster data of the same map. This paper proposes a practical solution for understanding of vector maps, including two major methoeds; ditching (DIrected Track stretCHING) method for open regions (e.g., roads, slopes and walls etc.) and inward tracing method for bounded regions (e.g., various fields).

A parallel blower system is quite familiar in hydraulic machine systems and quite often employed in many process industries. It is dynamically dual to the fundamental functional element of digital computer, that is, the flip-flop circuit, which was extensively studied by Moser. Although the global dynamic behaviour of such systems has significant bearing upon system operation, no substantial study reports have hitherto been presented. Extensive research concern has primarily been concentrated upon the local stability of the equilibrium point. In the paper, a piecewise linear model is used to analytically and numerically investigate its manifold global dynamic behaviour. To do this, first the Poincar map is defined as a composition boundary map, each of which is defined as the point transformation from the entry point to the end point of any trajectory on some boundary planes. It was already shown that, in some parameter region, the system exhibits the so-called chaotic states. The chaos generating process is investigated using the above Poincar map and it is shown that the map contains the contracting, stretching and folding operations which, as we often see in many cases particularly in horse shoe map, produce the chaotic states. Considering the one dimensional motions of the orbits by such Poincar map, that is, the stretching and folding operations, a one dimensional approximation of the Poincar map is introduced to more closely and exactly study manifold bifurcation processes and some illustrative bifurcation diagrams in relation to system parameters are presented. Thus it is shown how many types of bifurcations like the Hopf, period doubling, saddle node, and homoclinic bifurcations come to exist in the system.

We propose an asymmetric neural network which can solve inequality-constrained combinatorial optimization problems that are difficult to solve using symmetric neural networks. In this article, a knapsack problem that is one of such the problem is solved using the proposed network. Additionally, we study condition for obtaining a valid solution. In computer simulations, we show that the condition is correct and that the proposed network produces better solutions than the simple greedy algorithm.

We have fabricated a microchip of a neural circuit with pulse representation. The neuron output is a voltage pulse train. The synapse is a constant current source whose output is proportional to the duty ratio of neuron output. Membrane potential is charged by collection of synaptic currents through a RC circuit, providing an analog operation similar to the biological neural system. We use a 4-bit SRAM as the memory for synaptic weights. The expected I/O characteristics of the neurons and the synapses were measured experimentally. We have also demonstrated the capability of network operation with the use of synaptic weights, for solving the A/D conversion problem.

The data retention characteristics of a Flash memory cell with a self-aligned double poly-Si stacked structure have been drastically improved by applying a bi-polarity write and erase technology which uses uniform Fowler-Nordheim tunneling over the whole channel area both during write and erase. It is clarified experimentally that the detrapping of electrons from the gate oxide to the substrate results in an extended retention time. A bi-polarity write and erase technology also guarantees a wide cell threshold voltage window even after 106 write/erase cycles. This technology results in a highly reliable EEPROM with an extended data retention time.