We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.

Simple disjunctive decomposition is a special case of logic function decompositions, where variables are divided into two disjoint sets and there is only one newly introduced variable. It offers an optimal structure for a single-output function. This paper presents two techniques that enable us to apply simple disjunctive decompositions with little overhead. Firstly, we propose a method to find symple disjunctive decomposition forms efficiently by limiting decomposition types to be found to two: a decomposition where the bound set is a set of symmetric variables and a decomposition where the output function is a 2-input function. Secondly, we propose an algorithm that constructs a new logic representation for a simple disjunctive decomposition just by assigning constant values to variables in the original representation. The algorithm enables us to apply the decomposition with keeping good structures of the original representation. We performed experiments for decomposing functions and confirmed the efficiency of our method. We also performed experiments for restructuring fanout free cones of multi-level logic circuits, and obtained better results than when not restructuring them.

One-way sensing simple multihead finite automata with bounds on the number of times of use of sensing function in accepting computations are studied. It is shown that the languages accepted by one-way sensing simple multihead finite automata with constant sensing function bound satisfy the semilinear property, and that for one-way sensing simple multihead finite automata, m+1 times of the use of sensing function are better than m.

In this paper, we compare the performance of evolutionary digital filters (EDFs) for IIR adaptive digital filters (ADFs) in terms of convergence behavior and stability, and discuss their advantages. The authors have already proposed the EDF which is controlled by adaptive algorithm based on the evolutionary strategies of living things. This adaptive algorithm of the EDF controls and changes the coefficients of inner digital filters using the cloning method or the mating method. Thus, the adaptive algorithm of the EDF is of a non-gradient and multi-point search type. Numerical examples are given to demonstrate the effectiveness and features of the EDF such that (1) they can work as adaptive filters as expected, (2) they can adopt various error functions such as the mean square error, the absolute sum error, and the maximum error functions, and (3) the EDF using IIR filters (IIR-EDF) has a higher convergence rate and smaller adaptation noise than the LMS adaptive digital filter (LMS-ADF) and the adaptive digital filter based on the simple genetic algorithm (SGA-ADF) on a multiple-peak surface.

In a recent paper, Yang proposes an integer labeling algorithm for determining whether an arbitrary simplex P in Rn contains an integer point or not. The problem under consideration is a very difficult one in the sense that it is NP-complete. The algorithm is based on a specific integer labeling rule and a specific triangulation of Rn. In this paper we discuss a practical implementation of the algorithm and present a computer program (ILIN) for solving integer programming using integer labeling algorithm. We also report on the solution of a number of tested examples with up to 500 integer variables. Numerical results indicate that the algorithm is computationally simple, flexible, efficient and stable.

Linear programming techniques are useful in many diverse applications such as: production planning, energy distribution etc. To find an optimal solution of the linear programming problem, we have to repeat computations and it takes a lot of processing time. For high speed computation of linear programming, special purpose hardware has been sought. This paper proposes a systolic array for solving linear programming problems using the revised simplex method which is a typical algorithm of linear programming. This paper also proposes a modified systolic array that can solve linear programming problems whose sizes are very large.

Dynamic Term Rewriting Calculus is a new computation model proposed by the authors for the purpose of formal description and verification of algorithms treating Term Rewriting Systems. The computation of DTRC is basically term rewriting. The characteristic features of DTRC are dynamic change of rewriting rules during computation and hierarchical declaration of not only function symbols and variables but also rewriting rules. These features allow us to program metacomputation of TRSs in DTRC, that is , we can implement in DTRC in a natural way those algorithms which manipulate term rewriting systems as well as those procedures which verify such algorithms. In this paper, we give a formal description of DTRC. We then show some results on confluence property of DTRC.

In [2] Ibarra introduced a restricted version of one-way multihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k 1, simple (sensing) one-way (k + 1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way multihead PDA's

A uniquely decodable code pair (C, S) is considered for the two-user binary adder channel. When the first code C is linear, a lower bound of |S| is formulated and a uniquely decodable code pair (C, S) is presented. When a rate R1 of C is less than 1/3, a rate R2of S is greater than the best rate known previously.

This paper proposes a new digitized group modulator for radio base station transmitters of multi-carrier TDMA. This group modulator can flexibly set carrier spacing and features a simple construction as a result of employing the Simple Fractional Sampling technique. A group modulator LSI was designed and built using 0.5-µm BiCMOS technology, and a π/4-shifted QPSK group modulator was constructed using this LSI. Experiments confirm that the modulator simultaneously generates multiple carriers in a wide bandwidth without the need for precise adjustment and there is little difference between each of the carriers in terms of BER performance. Moreover, experiments confirm that the group modulator's burst-output (frequency hopping) performance is excellent.

A uniquely decodable (UD) code pair (C, S) is considered for the two-user binary adder channel. For a class of linear codes C, the maximum independent set of the graph associated with C, which is the second code S, is evaluated. When the rate R1 of C is less than 0.5, there exist UD codes (C, S)'s such that the rate R2 of S exceeds the Khachatrian's and Guo's results in amount.

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.

We propose a new architecture of Functional Memory type Parallel Processor (FMPP) architectures called bit-parallel block-parallel (BPBP) FMPP. Design details of a prototype BPBP FMPP chip are also shown. FMPP is a massively parallel processor architecture that has a memory-based simple two-dimensional regular array structure suitable for memory VLSI technology. Computation space increases as integration density of memory increases. Computation time does not depend on the number of processors. So far, a bit-serial word-parallel (BSWP) implementation based on a content addressable memory (CAM) is mainly investigated as one of promising architectures of FMPP. In a BSWP FMPP, each word of a CAM works as a processor, and the amount of hardware is minimized by abopting a bit-serial operation, thus maximizing integration scale. The BSWP FMPP, however, does not allow operations between two words, which restriction limits the applicability of the BSWP FMPP. On the other hand, the proposed BPBP FMPP is designed to execute logical and arithmetic operations on two words. These operations are performed simultaneously on every group of words called a block. BPBP FMPP hereby achieves a high performance while maintaining high integration density of the BSWP, and is suitable for various applications.