Although many successful asynchronous control circuit synthesis methods are available, it is still unwieldy to conceive and describe the behaviors of a number of controllers which constitute a control unit of a target system manually. In this paper, an automatic and systematic method to derive an efficient asynchronous control unit from a system specification, a control data flow graph (CDFG), is suggested. In order to acquire an asynchronous control unit of acceptable quality, a new process-oriented method is proposed. In this method, the resulting asynchronous control unit has complete separation of 'execution controllers' and 'execution order controllers' according to the hierarchical decomposition of a given CDFG. This distributive feature leads to a significant improvement in area, performance, implementability and synthesis time for the derived asynchronous control units.

In this paper, usage of undefined states on a State Transition Graph (STG) is addressed to obtain high fault coverage, in the area of Synthesis For Testability (SFT) of synchronous sequential circuits. Basically, a given STG could be modified by adding undefined states and distinguishable transitions so that each state might be included in one strongly-connected component as much as possible. Such modification decreases the number of redundant faults caused by the existence of unreachable states on an STG. For the modification, we propose two algorithms for both incompletely-specified STGs and completely-specified STGs, respectively. In case of incompletely-specified STGs, undefined states are added using unspecified transitions of defined states. In case of completely-specified STGs, undefined states are added by changing transitions specified on an STG while preserving state equivalence. Experimental results with MCNC benchmarks show that the number of redundant faults of gate-level circuits synthesized by our modified STGs are reduced, resulting in high fault coverage as well as short test generation time

This paper presents a new asynchronous multiplier. The original array structure is divided into two asymmetric arrays, called an upper array and a lower array. For the lower array, Left to Right scheme is applied to take advantage of a fast computation and low power consumption as well. Simulation results show that the proposed multiplier has 40% of performance improvement with a relatively lower power consumption. The multiplier has been implemented in a CMOS 0.35 µm technology and proved functionally correct.

There is an ever-increasing demand for better performance and scalability in workflow systems. We describe how mobile agents can be used to satisfy such a requirement. For the purpose two important design issues are pointed out in workflow execution and architecture levels. Agent delegation models and a 3-layer architecture are suggested in mobile agent based workflow systems as a solution for each consideration. Workload is statically distributed over task performers based on the proposed method. As a result the performance and the scalability are improved. The effectiveness is shown through stochastic Petri-nets simulation through comparison with client-server based- and another mobile agent-based workflow systems.

In this paper, we propose an advanced structure of the interface circuit, called a wrapper, for Globally Asynchronous Locally Synchronous (GALS) systems. The proposed wrapper is composed of a sender module and a receiver module. The sender module carries out data transfers in an efficient way by decoupling dependency between an external handshake protocol and an internal clock. The decoupling effect allows the external handshake protocol and the internal clock to be executed in a concurrent way and hence allows the wrapper to show better performance. We have designed our wrapper at the transistor level with 0.35-µm technology. When we compare our decoupled wrapper with two conventional wrappers based on pausible clocking scheme, our simulation results show that performance improvement is about 8-13% and 13-56%, respectively.

Free choice nets are a class of Petri nets, which can represent the substantial features of systems by modeling both choice and concurrency. And in the modelling and design of a large number of concurrent systems, live and safe free choice nets (LSFC nets) have been explored their structural characteristics. On the other hand, state machine decomposable nets (SMD nets) are a class of Petri nets which can be decomposed by a set of strongly connected state machines (S-decomposition). State machine allocatable nets (SMA nets) are a well-behaved class of SMD nets. Of particular interest is the relation between free choice nets and SMA nets such that a free choice net has a live and safe marking if and only if the net is an SMA net. That is, the structure of an LSFC net is an SMA net. Recently, the structure of SMA net has been completely characterized by the authors based on an S-decomposition. In other words, a necessary and sufficient condition for a net to be an SMA net is obtained in terms of the net structure where synchronization between strongly connected state machine components (S-components) has been clarified. Unfortunately, it requires tremendous amount of time and spaces to decide a given net to be an SMA net by applying the condition directly. Moreover, there exist no efficient algorithm to decide the liveness and safeness of a given SMA net that lessens the usefulness of decomposition techniques. In this paper, we consider efficient polynomial order algorithms to decide whether a given net is a live and safe SHA net.

Basic structural characteristics, which are useful in modular synthesis based on strongly connected state machines, of SMA/LBFC nets are discussed in this paper. A more convincing and direct proof of the equivalence of two structural characterization of the class of Petri nets is given. This proof will give clearer view of the structural characteristics of LBFC/SMA nets. On the other hand, however, the structural characteristics are not practically amenable in application to modular synthesis of SMA nets from a given set of SCSM's since all possible SCSM's should be examined for the verification of the given conditions. The later half of this paper is devoted into strengthening the results, i. e. , in composition of an SMA net from a given set of SCSM's the condition is also satisfied in any SCSM generated by composition.

Unfolding originally introduced by McMillan is gaining ground as a partial-order based method for the verification of concurrent systems without state space explosion. However, it can be exposed to redundancy which may increase its size exponentially. So far, there have been trials to reduce such redundancy resulting from conflicts by improving McMillan's cut-off criterion. In this paper, we show that concurrency is also another cause of redundancy in unfolding, and present an algorithm to reduce such redundancy in live, bounded and reversible Petri nets which is independent of any cut-off algorithm.

In this paper, we propose an approach to test pattern generation for Speed-Independent (SI) asynchronous control circuits. Test patterns are generated based on a specified sequence, which is derived from the specification of a target circuit in the form of a Signal Transition Graph (STG). Since the sequence represents the behavior of a circuit only with stable states, the state space of the circuit can be represented as reduced one. A product machine, which consists of a fault-free circuit and a faulty circuit, is constructed and then the specified sequence is applied sequentially to the product machine. A fault is detected when the product machine produces inconsistency, i.e., output values of a fault-free circuit and a faulty circuit are different, and the sequentially applied part of the sequence becomes a test pattern to detect the fault. We also propose a test generation method using an undetectable fault identification as well as the specified sequence. Since the reduced state space is a subset of that of a gate level implementation, test patterns based on a specification cannot detect some faults. The proposed method identifies those faults with a circuit topology in advance. BDD is used to implement the proposed methods efficiently, since the proposed methods have a lot of state sets and set operations. Experimental results show that the test generation using a specification achieves high fault coverage over single stuck-at fault model for several synthesized SI circuits. The proposed test generation using a circuit topology as well as a specification decreases execution time for test generation with negligible cost retaining high fault coverage.

The current scheme of access control judges the legality of each access based on immediate information without considering associate information hidden in a series of accesses. Due to the deficiency, access control systems do not efficiently limit attacks consist of ordinary operations. For trusted operating system developments, we extended RBAC and added negative procedural constraints to refuse those attacks. With the procedural constraints, the access control of trusted operating systems can discriminate attack trials from normal behaviors. This paper shows the specification of the extended concept and model, and presents simple analysis results.

In this paper, an approach to derive a logic function of asynchronous circuits from a graph-based model called Signal Transition Graphs (STG) is discussed. STG's are Petri nets, whose transitions are interpreted as a signal transition on the circuit inputs or gate outputs, and its marking represents a binary state of the circuit. STG's can represent a behavior of circuit, to derive logic functions, however, the reachability graph should be constructed. In the verification of STG's some method based on Occurrence nets (OCN) and its prefix, called unfolding, has been proposed. OCN's can represent both causality and concurrency between two nodes by net structure. In this paper, we propose a method to derive a logic function by generating substate space of a given STG using the structural properties of OCN. The proposed method can be seem as a parallel algorithm for deriving a logic function.

In this paper, we have proposed an efficient high-level test generation method for asynchronous circuits. The test generation is based on specification level, especially on Signal Transition Graph (STG), which is a kind of specification method for asynchronous circuits. We define a high-level fault model, called a single State Transition Fault (STF) model on STG. Test patterns for STFs are generated based on Stable State Graph (SSG), which can be derived from STG directly. The state space explored in test generation is greatly reduced and hence the test generation cost is small in terms of execution time. To enhance the fault coverage at gate-level, we have also proposed an extended STF (ESTF) model with additional gate-level information. Experimental results show that the generated test for STFs achieves high fault coverage with low cost for single stuck-at faults of its corresponding synthesized gate-level circuit. The generated test for ESTFs attains higher fault coverage with same benchmark in cost of longer execution time. Further, we have also proposed a 3-phase test generation based on the above proposed methods. An effective test generation is implemented by 3-phase: 1) test generation for STFs, 2) test generation for ESTFs, and 3) test generation using an asynchronous product machine traversal method. Experimental results also show that the proposed 3-phase test generation achieves higher fault coverage in cost of longer execution time.

We introduce a high-level synthesis framework to automatically synthesize asynchronous circuits, especially speed-independent circuits, from a concurrent programming language called ALPEH. ALPEH is a high-level concurrent algorithmic specification that can model complex concurrent control flows, logical and arithmetic computations, and communications in easy way. This specification language has been developed to be translated into a Petri net. The major contribution of this paper is the generation of globally optimized control circuits during preserving neat formalism in the specification.

A job shop system typically seen in flexible manufacturing systems (FMS) is a system composed of a set of machines and a various kind of jobs processed with the machines. A production system of semiconductor fabrication is an example of job shop systems, which has main features of repetitive processes of one part and set-up times required for machines processing different types of parts. On the other hand, timed Petri nets are used for modelling and analyzing a wide variety of discrete event systems. There are many applications of timed Petri nets to the scheduling problems of job shop systems. The performance evaluation and steady state behaviors are studied by using the maximum cycle time of timed marked graphs. The aim of this paper is to propose a new model for production systems including repetitive processes and set-up time requirements which enables the quantitative analysis of real time system performance. In job shop systems such as a semiconductor fabrication system, it takes considerable amount of set-up time to prepare different types of chemical reactions and the model should take account of a set-up time for each machine. We focus upon the relationship between facility utilization factor and production cycle time in the steady state. In the proposed model, the minimum total set-up time can be attained. Quantitative relationship between utilization factor and production cycle time is derived by using the proposed model. A utilization factor of a system satisfying a given limit of the cycle time is evaluated, and the improvement of the utilization factor is considered. Conversely, we consider the improvement of the cycle time of a system satisfying a given limit of utilization factor.

A reachability theorem for a class of live and safe free choice nets (LSFC nets) is presented in this paper. A necessary and sufficient condition for the reachability of a class of LSFC net is derived based on the associated digraph.

Modular design of concurrent systems can be based on concrete net composition techniques. For example, to design a discrete event systems with some desirable properties such as liveness and safeness by composition of simple subsystems (modules), specific rules of composition have to be found. Unfortunately, there exist no general techniques to guarantee the overall properties by net composition except for a restricted case of the stepwise refinement. In this paper, we conduct a necessary and sufficient condition for a net composition to guarantee the composed net fallen into an important subclass of Petri nets. A free choice nets is a class of Petri nets, which can represent the substantial feature of systems by modeling both choice and concurrency. A state machine decomposable nets (SMD nets) is a class of nets composed by a set of strongly connected state machines (SCSMs). A state machine allocatable nets (SMA nets) is a class of SMD nets in which the way of SCSM composition is implicitly restricted by the definition. The structural characterization of SMA nets has originally been considered by Hack. The aim of this paper is to clarify the restrictions on SCSM composition for SMA nets and to derive the complete structural characterization of this class of nets. The problem can be viewed as to find the structure of the synchronization between SCSMs to yield relevant properties such as SMA nets. Esparza and Silva have investigated the same problem and derived a necessary and sufficient condition for a net to be an SMA net. The condition obtained in this paper is more explicit and simple with respect to the way of SCSM composition. The importance of investigating the structural properties of SMA net can be understood by the fact that a free choice net is live and safe if and only if the net is an SMA net, and to synthesize a live and safe free choice net is often the goal of correct concurrent system design.

This paper deals with security issues in a mobile agent system, especially protecting agent data from malicious servers. For this purpose, one-time key generation system, OKGS in short, is proposed. In OKGS, we integrate notions of an one-way hash function and a coupler. A one-way function plays a major role in ensuring confidentiality and integrity of agent data. And the notion of a coupler is used to establish inter-relationship among consecutive encryption keys for agent data, i.e,. all agent keys form a unidirectional chain. With these two features of OKGS, therefore, only the agent owner, who creates the agent bearing data, can decrypt and protect all agent data which are gathered in its itinerary.