IEICE TRANSACTIONS on Fundamentals

  • Impact Factor

    0.40

  • Eigenfactor

    0.003

  • article influence

    0.1

  • Cite Score

    1.1

Advance publication (published online immediately after acceptance)

Volume E79-A No.11  (Publication Date:1996/11/25)

    Special Section on Description Models for Concurrent Systems and Their Applications
  • FOREWORD

    Kunihiko HIRAISHI  

     
    FOREWORD

      Page(s):
    1751-1751
  • Reuse Based Specification Support Method Using Mathematical Similarity

    Ushio YAMAMOTO  Eun-Seok LEE  Norio SHIRATORI  

     
    PAPER

      Page(s):
    1752-1759

    In this paper, we discuss both effective approaches in specification process, formal specification and reuse, and focus on providing an integrated and systematic supportbased on them. Preparing the specification model which mediates an image of the designer and another representation of it in formal method, the designer can specify the target system incrementally and smoothly. As for the specification model, we employ LTS on the early step of specification process because of its understandability for the designer. Moreover, reuse of specification leads to reduction of the cost and time, defining retrieval mechanism of reusable cases from database by mathematically calculating similarity of them. For the reuse mechanism, we define a new concept of similarity on LTS as the criterion of case retrieval, which enables more flexible matching between the besigner's requirement and the existing case than any other traditional schema on LTS, and show the case retrieval algorithm. Integration of two approaches brings us the great improvement of the productivity on system development.

  • A Topological Framework of Stepwise Specification for Concurrent Systems

    Toshihiko ANDO  Kaoru TAKAHASHI  Yasushi KATO  

     
    PAPER

      Page(s):
    1760-1767

    We present a topological framework of stepwise specification for concurrent systems in this paper. Some of description techniques can make topologies on the system space. Such topologies corresponds to abstract levels of those description techniques. Using a family of such description techniques, one can specify systems stepwisely. This framework allows to bridge various DTs and modularizing, so that global properties and module properties of systems become to be related to each other. Within this framework, we show derivation of a LOTOS cpecification from temporal logic formulae. An extended version of LOTOS with respect to concurrency is used in this paper. A semantics including concurrency is introduced to do this in this method. The method presented in this paper is applied to mobile telecommunication.

  • Introduction of Economic-Oriented Fairness to Process Algebras

    Shigetomo KIMURA  Yoshihiko EBIHARA  

     
    PAPER

      Page(s):
    1768-1773

    Fairness is one of the important notion for programming language, such as process algebras like CCS, that includes concurrency (or parallelism) and nondeterminism. This ensures that while repeatedly choosing among a set of alternatives, no alternative will be postponed forever. However, the fairness does not mention at what frequency these alternatives are selected. In this paper, we propose a quantitative fairness, which is called economic-oriented fairness, to each alternatives. This fairness ensures that the expected number of selection for each alternatives are same. We give a condition for probability assignment of selection of each alternative to be satisfied for economic-oriented fairness. First we show a simple probability assignment rule. In this assignment, between any two alternatives, if an alternative is selected n times and the other m times then the probability to select the former alternative is (m + 1)/(n + 1) times the probability for the latter. We prove that this assignment satisfies the condition of economic-oriented fairness. For a model of the economic-oriented fairness, we adopt a probabilistic process algebra. Finally, we elaborate with two process models of the economic-oriented fairness. The first one is a server and client model, where each client communicates only with the server, but not among them. In this model, the expected number of communication by each client are equal. The second model considers communication between two processes. In practice, a process has several subprocesses. Each subprocess communicates via a communication port, In the second model, there is economic-oriented fairness where the expected number of communications via each communication port are equal.

  • A GA Approach to Solving Reachability Problems for Petri Nets

    Keiko TAKAHASHI  Masayuki YAMAMURA  Shigenobu KOBAYASHI  

     
    PAPER

      Page(s):
    1774-1780

    In this paper we present an efficient method to solve reachability problems for Petri nets based on genetic algorithms and a kind of random search which is called postpone search. Genetic algorithm is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.

  • Non-Regenerative Stochastic Petri Nets: Modeling and Analysis

    Qun JIN  Yoneo YANO  Yoshio SUGASAWA  

     
    PAPER

      Page(s):
    1781-1790

    We develop a new class of stochastic Petri net: non-regenerative stochastic Petri net (NRSPN), which allows the firing time of its transitions with arbitrary distributions, and can automatically generate a bounded reachability graph that is equivalent to a generalization of the Markov renewal process in which some of the states may not constitute regeneration points. Thus, it can model and analyze behavior of a system whose states include some non-regeneration points. We show how to model a system by the NRSPN, and how to obtain numerical solutions for the NRSPN model. The probabilistic behavior of the modeled system can be clarified with the reliability measures such as the steady-state probability, the expected numbers of visits to each state per unit time, availability, unavailability and mean time between system failure. Finally, to demonstrate the modeling ability and analysis power of the NRSPN model, we present an example for a fault-tolerant system using the NRSPN and give numerical results for specific distributions.

  • On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule

    Atsushi OHTA  Tomiji HISAMURA  

     
    PAPER

      Page(s):
    1791-1796

    Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations among three types of reachability are considered from the viewpoint of the earliest firing rule. Since earliest firing systems can simulate register machines, they have equivalent modeling powers to Turing machines. It suggests, however, that most of the analysis problems of earliest firing systems with general net structures are undecidable. In this paper, net structures are restricted to a subclass called dissynchronous choice (DC) nets. It is shown that the reachability problem from an initial marking to dead markings (markings where no transition can fire) in earliest firing DC systems is equivalent to the usual reachability problem of the same systems under the normal firing rule. Then, the result is applied to reachability problems of controlled DC systems in which some transitions in the net have external control input places. It is shown that for systems where every transition in the net has an external control input place, one type of reachability problem is decidable. Lastly, the liveness problem of earliest firing DC systems is considered and it is shown that this problem is equivalent to that of the underlying DC system under the normal firing rule. It is also shown that this liveness problem is decidable.

  • A High-Level Petri Net for Accurate Modeling of Reactive and Concurrent Systems

    Naoshi UCHIHIRA  Shinichi HONIDEN  

     
    PAPER

      Page(s):
    1797-1808

    This paper concerns a Petri-net-based model for describing reactive and concurrent systems. Although many high-level Petri nets have been proposed, they are insufficiently practical to describe reactive and concurrent systems in the detail modeling, design and implementation phases. They are mainly intended to describe concurrent systems in the rough modeling phase and lack in several important features (e.g., concurrent tasks, task communication/synchronization, I/O interface, task scheduling) which the most actual implementations of reactive and concurrent systems have. Therefore it is impossible to simulate and analyze the systems accurately without explicitly modeling these features. On the other hand, programming languages based on Petri nets are deeply dependent on their execution environments and not sophisticated as modeling and specification languages. This paper proposes MENDEL net which is a high-level Petri net extended by incorporating concurrent tasks, task communication/synchronization, I/O interface, and task scheduling in a sophisticated manner. MENDEL nets are a wide-spectrum modeling language, that is, they are suitable for not only modeling but also designing and implementing reactive and concurrent systems.

  • A Graph Theoretic Approach to Reachability Problem with Petri Net Unfoldings

    Toshiyuki MIYAMOTO  Sadatoshi KUMAGAI  

     
    PAPER

      Page(s):
    1809-1816

    Petri nets are widely recognized as a powerful model for discrete event systems. Petri nets have both graphical and mathematical features. Graphical feature provides an environment to design and to comprehend discrete event systems. Mathematical feature provides an analysis power for verifying several properties of such systems. Several analysis techniques have been proposed so far, such as a reachability (coverability) graph method, a matrix equation approach, reduction or decomposition techniques, a symbolic model method and an unfolding method. The unfolding method was introduced to avoid generating the reachability graph. Unfoldings are often used in the verification of asynchronous circuits. This paper focuses on an analysis of finite state systems, i.e., bounded nets, and discuss a reachability problem and a upper bound problem. Relations between these problems and an unfolding have been clarified to provide a novel method to resolve these problems.

  • Finding Minimal Siphons in General Petri Nets

    Shinji TANIMOTO  Masahiro YAMAUCHI  Toshimasa WATANABE  

     
    PAPER

      Page(s):
    1817-1824

    A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.

  • Finding a Minimal Siphon Containing Specified Places in a General Petri Net

    Masahiro YAMAUCHI  Shinji TANIMOTO  Toshimasa WATANABE  

     
    LETTER

      Page(s):
    1825-1828

    A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. The subject of the paper is to find a minimal siphon containing a given set of specified places of a general Petri net.

  • A Consideration of Transient Characteristics on Throughput in a Slotted Ring Network

    Ken TERUYA  Norio SHIRATORI  

     
    LETTER

      Page(s):
    1829-1834

    We have previously reported studies [3], [4] of the steady state system throughput in a slotted ring network. In this paper, we analyze the transient state of packet transmission and derive several characteristics of the network.

  • Special Section of Letters Selected from the 1996 IEICE General Conference
  • FOREWORD

    Hajime MAEDA  

     
    FOREWORD

      Page(s):
    1835-1835
  • Speech Recognition Based on Fusion of Visual and Auditory Information Using Full-Framse Color Image

    Satoru IGAWA  Akio OGIHARA  Akira SHINTANI  Shinobu TAKAMATSU  

     
    LETTER

      Page(s):
    1836-1840

    We propose a method to fuse auditory information and visual information for accurate speech recognition. This method fuses two kinds of information by using Iinear combination after calculating two kinds of probabilities by HMM for each word. In addition, we use full-frame color image as visual information in order to improve the accuracy of the proposed speech recognition system. We have performed experiments comparing the proposed method with the method using either auditory information or visual information, and confirmed the validity of the proposed method.

  • Negative-Resistance Analysis of Colpitts Crystal Oscillators with a Tank Circuit

    Masayuki HANAZAWA  Yasuaki WATANABE  Hitoshi SEKIMOTO  

     
    LETTER

      Page(s):
    1841-1843

    This paper describes a circuit analysis technique that includes all circuit elements used in transistor Colpitts quartz crystal oscillators. This technique is applied to a quartz crystal oscillator that has a tank circuit for selecting the oscillation frequency. The results obtained with this technique are compared with SPICE simulation results. Good agreement in the results clearly shows the validity of our technique.

  • On Unstable Saddle-Node Connecting Orbit in a Planer Autonomous System

    Tetsushi UETA  Hiroshi KAWAKAMI  

     
    LETTER

      Page(s):
    1844-1847

    We found a novel connecting orbit in the averaged Duffing-Rayleigh equation. The orbit starts from an unstable manifold of a saddle type equilibrium point and reaches to a stable manifold of a node type equilibrium. Although the connecting orbit is structurally stable in terms of the conventional definition of structural stability, it is structually unstable since a one-deimensional manifold into which the connecting orbit flows is unstable. We can consider the orbit is one of global bifurcations governing the differentiability of the closed orbit.

  • Estimation of Muscle Fatigue of Low Back on a Vehicle Seat

    Hisao OKA  Shiro FUJIWARA  Masakazu OSHIMA  Hiroshi KISHIMOTO  

     
    LETTER

      Page(s):
    1848-1850

    The aim of this study is to measure and quantify muscle fatigue of low back, caused by sitting on the vehicle seat for a long period of time. The authors proposed a new objective muscle fatigue index based on Principle Component Analysis utilizing the measured muscle viscoelasticity and EMG. The new index suggests an adequate correlation with the subjective fatigue.

  • The Upper Limit of a Parameter for a Two-Stroke Oscillator to Have a Stable Limit Cycle

    Yasumasa SUJAKU  Takahiro YAMADA  Tosiro KOGA  

     
    LETTER

      Page(s):
    1851-1852

    A type of Lienard's equation f(x)+x=0, where f(x) is not an even function of x, is studied by Le Corbeiller as a model of various biological oscillations, such as breathing, and called two-stroke oscillators. A distinctive feature of this type of oscillators is that the parameter µ has the upper limit µ0 for the oscillator to have some stable limit cycle. This paper gives a numerical method for calculating this upper limit µ0.

  • A Map Matching Method with the Innovation of the Kalman Filtering

    Takashi JO  Miki HASEYAMA  Hideo KITAJIMA  

     
    LETTER

      Page(s):
    1853-1855

    This letter proposes a map-matching method for automotive navigation systems. The proposed method utilizes the innovation of the Kalman filter algorithm and can achieve more accurate positioning than the correlation method which is generally used for the navigation systems. In this letter, the performance of the proposed algorithm is verified by some simulations.

  • Distributed Stable Marriage of Autonomous Mobile Robots and Battery Charger Station

    Hideki KINJO  Morikazu NAKAMURA  Kenji ONAGA  

     
    LETTER

      Page(s):
    1856-1859

    In this paper, we propose the distributed stable marriage problem and apply it to planning for cooperative works of autonomous mobile robots and battery charger stations. We develop and analyze a distributed algorithm to determine the partner by message communication.

  • Radiation Fields of a Printed-Dipole on a Semi-Infinite Substrate

    Tomotaka WADA  Masanobu KOMINAMI  Hiroji KUSAKA  

     
    LETTER

      Page(s):
    1860-1861

    The printed dipole on a semi-infinite substrate is investigated. The solution is based on the moment method in the Fourier transform domain. We analyze far-field and near-field radiation patterns for a printed dipole. Therefore, we make radiation fields clear.

  • Regular Section
  • An Extended Lattice Model of Two-Dimensional Autoregressive Fields

    Takayuki NAKACHI  Katsumi YAMASHITA  Nozomu HAMADA  

     
    PAPER-Digital Signal Processing

      Page(s):
    1862-1869

    We present an extended quarter-plane lattice model for generating two-dimensional (2-D) autoregressive fields. This work is a generalization of the extended lattice filter of diagonal form (ELDF) developed by Ertuzun et al. The proposed model represents a wider class of 2-D AR fields than conventional lattice models. Several examples are presented to demonstrate the applicability of the proposed model. Furthermore, the proposed structure is compared with other conventional lattice filters based on the computation of their entropy values.

  • A New Time-Domain Design Method of IIR Approximate Inverse Systems Using All-Pass Filters

    Md. Kamrul HASAN  Takashi YAHAGI  

     
    PAPER-Digital Signal Processing

      Page(s):
    1870-1878

    This paper is devoted to a new design method for infinite impulse response approximate inverse system of a nonminimum phase system. The design is carried out such that the convolution of the nonminimum phase polynomial and its approximate inverse system can be represented by an approximately linear phase all-pass filter. A method for estimating the time delay and order of an approximate inverse system is also presented. Using infinite impulse response approximate inverse systems better accuracy is achieved with reduced computational complexity. Numerical examples are included to show the effectiveness of the proposed method.

  • Simultaneous Approximation for IIR Digital Filters with Log Magnitude and Phase Response

    Masahiro OKUDA  Masaaki IKEHARA  Shin-ichi TAKAHASHI  

     
    PAPER-Digital Signal Processing

      Page(s):
    1879-1885

    In this paper, we propose a new design algorithm for nearly linear phase IIR digital filters with prescribed log magnitude response. The error function used here is the sum of the weighted log magnitude-squared error and phase -squared error, and so it is possible to control log magnitude and phase response directly. The gradient vector of the proposed error function is easily calculated as the closed form solution because of its nature, in which the real and imaginary part of the logarithm of a complex transfer transfer function corresponds to the log magnitude and phase response, respectively. This algorithm is simple and converges quickly. Finally, we show the validity of the proposed algorithm with some examples.

  • An Adaptive Learning and Self-Deleting Neural Network for Vector Quantization

    Michiharu MAEDA  Hiromi MIYAJIMA  Sadayuki MURASHIMA  

     
    PAPER-Nonlinear Problems

      Page(s):
    1886-1893

    This paper describes an adaptive neural vector quantization algorithm with a deleting approach of weight (reference) vectors. We call the algorithm an adaptive learning and self-deleting algorithm. At the beginning, we introduce an improved topological neighborhood and an adaptive vector quantization algorithm with little depending on initial values of weight vectors. Then we present the adaptive learning and self-deleting algorithm. The algorithm is represented as the following descriptions: At first, many weight vectors are prepared, and the algorithm is processed with Kohonen's self-organizing feature map. Next, weight vectors are deleted sequentially to the fixed number of them, and the algorithm processed with competitive learning. At the end, we discuss algorithms with neighborhood relations compared with the proposed one. The proposed algorithm is also good in the case of a poor initialization of weight vectors. Experimental results are given to show the effectiveness of the proposed algorithm.

  • Independent Spanning Trees of Product Graphs and Their Construction

    Koji OBOKATA  Yukihiro IWASAKI  Feng BAO  Yoshihide IGARASHI  

     
    PAPER-Graphs and Networks

      Page(s):
    1894-1903

    A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G1 is an n1-channel graph and G2 is an n2-channel graph, then G1G2 is an (n1 + n2)-channel graph. We prove this fact by a construction of n1+n2 independent spanning trees of G1G2 from n1 independent spanning trees of G1 and n2 independent spanning trees of G2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.

  • Modification of LZSS by Using Structures of Hangul Characters for Hangul Text Compression

    Jae Young LEE  Keong Mo SUNG  

     
    PAPER-Information Theory and Coding Theory

      Page(s):
    1904-1910

    This paper suggests modified LZSS which is suitable for compressing Hangul data by Hangul character token and the string token with small size based on Hangul properties. The Hangul properties can be described in 2 ways. 1) The structure of a Hangul character consists of 3 letters: The first sound letter, the middle sound letter, and the last sound letter which are called Cho-seong, Jung-seong, and Jong-seong, respectively. 2) The code of Hangul is represented by 2 bytes. The first property is used for making the character token processing Hangul characters which occupies most of the unmatched characters. That is, the unmatched Hangul characters are replaced with one Hangul character token represented by Huffman codes of Cho-seong, Jung-seong, and Jong-seong in regular sequence, instead of 2 character tokens. The second property is used to shorten the size of the string token processing matched string. In other words, since more than 75% of Hangul data are Hangul and Hangul codes are constructed in 2 bytes, the addresses of the window of LZSS can be assigned in 2-byte unit. As a result, the distance field and the length field of the string token can be lessened by one bit each. After compressing Hangul data through these tokens, about 3% of improvement could be made in compression ratio.

  • Matched Design Method for Concatenated Trellis-Coded Modulation

    Tadashi WADAYAMA  Koichiro WAKASUGI  Masao KASAHARA  

     
    PAPER-Information Theory and Coding Theory

      Page(s):
    1911-1917

    A new design method, which is referred to as the matched design method, for concatenated trellis-coded modulation (TCM) is presented. Most of the conventional concatenated TCM employs TCM designed to maximize the minimum squared Euclidean free distance, d2free. With the matched design method, we maximize d21(t) instead of d2free, where d21(t) is the effective minimum squared Euclidean distance (MSED) when the outer code has a t-error correcting capability. The effective MSED is derived from the Euclidean/Hamming (E/H) joint weight distribution of terminated TCM. We here assume the concatenated TCM whose transmitted symbol corresponds to a symbol of outer code. The new classes of 2-dimensional (2D) and 4-dimensional (4D) codes are found by a computer search. Under the performance measures of the effective MSED or the effective multiplicity, these codes are superior to the conventional codes such as the Ungerboeck's 2D-codes when those are used as an inner code. We disclose an interesting fact that the new class of codes using rate-1/2 encoder is superior to the class of codes using rate-2/3 encoder. This fact implies that the codes using rate-1/2 encoder have two advantages: 1) better overall decoding performance and 2) less decoding complexity.

  • Reduction of Computational Complexity in the IA Algorithm

    Isao NAKANISHI  Yoshio ITOH  Yutaka FUKUI  

     
    LETTER-Digital Signal Processing

      Page(s):
    1918-1921

    For reduction of computational complexity in the IA algorithm, the thinned-out IA algorithm in which only one step size is updated every iteration is proposed and is complementarily switched with the HA algorithm according to the convergence. The switching is determined by using the gradient of the error signal power. These are investigated through the computer simulations.

FlyerIEICE has prepared a flyer regarding multilingual services. Please use the one in your native language.