On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule (Special Section on Description Models for Concurrent Systems and Their Applications)
スポンサーリンク
概要
- 論文の詳細を見る
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 ma-chines. 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 ratability problem is decidable. Lastly, the livens 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.
- 社団法人電子情報通信学会の論文
- 1996-11-25
著者
-
OHTA Atsushi
NTT Network Innovation Laboratories, NTT Corporation
-
Ohta Atsushi
Ntt Network Innovation Laboratories Ntt Corporation
-
Ohta Atsushi
Ntt Corporation
-
Ohta A
Ntt Network Innovation Laboratories Ntt Corporation
-
Hisamura Tomiji
The School Of Science And Engineering Waseda University
-
OHTA Atsushi
the School of Science and Engineering, Waseda University
関連論文
- A New User Selection Measure in Block Diagonalization Algorithm for Multiuser MIMO Systems
- New Robust Beamforming Method for Frequency Offsets in Uplink Multiuser OFDM-MIMO(Smart Antennas,2006 International Symposium on Antennas and Propagation)
- New Downlink Beamforming Method for Cooperative Multiple Access Point Systems(Smart Antennas,2006 International Symposium on Antennas and Propagation)
- A Reduced-Complexity Signal Detection Scheme Employing ZF and K-Best Algorithms for OFDM/SDM(Space Division Multiplexing)(Multi-carrier Signal Processing Techniques for Next Generation Mobile Communications-Part 1)
- A New User Selection Measure in Block Diagonalization Algorithm for Multiuser MIMO Systems
- Antenna Selection Method for Terminal Antennas Employing Orthogonal Polarizations and Patterns in Outdoor Multiuser MIMO System
- A Synchronization Scheme for Packet Mode MIMO-OFDM Signals in Wireless LAN(Terrestrial Radio Communications)
- A Scheme to Evaluate Cell Throughput of Multi-Rate Wireless LAN Systems with CSMA/CA(Wireless Communication Technology)
- A Simple and Feasible Decision-Feedback Channel Tracking Scheme for MIMO-OFDM Systems(Advanced Transfer Technologies for the Next Generation Network)
- B-5-12 A New Fast Layered Ordering Method for MIMO Decision Feedback Equalization
- A Simplified Maximum Likelihood Detector for OFDM-SDM Systems in Wireless LAN(2004 International Symposium on Antennas and Propagation)
- B-5-196 A Novel QR-Decomposition-Aided Near Maximum Likelihood Detector in OFDM-SDM Systems(B-5. 無線通信システムB(ワイヤレスアクセス), 通信1)
- FPGA Implementation of Eigenbeam MIMO-OFDM for Wireless LAN and Its Experimental Performance(Software Defined Radio Technology and Its Applications)
- On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule (Special Section on Description Models for Concurrent Systems and Their Applications)