Accession Number : ADA297111

Title :   Decision Problems Related to Structural Induction for Rings of Petri Nets with Fairness,

Corporate Author : WISCONSIN UNIV-MILWAUKEE DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Personal Author(s) : Li, Jianan ; Suzuki, Ichiro ; Yamashita, Masafumi

PDF Url : ADA297111

Report Date : OCT 1995

Pagination or Media Count : 6

Abstract : Structural induction is a technique for proving that a system consisting of many identical components works correctly regardless of the actual number of components it has. Previously the authors have obtained conditions under which structural induction goes through for rings that are modeled as a Petri net satisfying a fairness requirement. The conditions guarantee that for some all rings of size k or greater exhibit similar behavior. The key concept is the similarity between rings, where rings Rk and Rl of sizes k and l, respectively, are said to be similar if, intuitively, none of the components in either ring can tell whether it is in Rk or Rl, and none of the components (except possibly one) can tell its position within the ring to which it belongs. A ring satisfying this second property is said to be uniform. In this paper we prove the undecidability of various basic questions regarding similarity and uniformity. Some of the questions shown to be undecidable are: Is there k such that 1?k and pk+l are similar? Is there k such that all rings of size k or greater are mutually similar? Is there k such that Rk is uniform? Is there k such that 1?k, Rk+l, Rk+2,... are all uniform? (AN)

Descriptors :   *NEURAL NETS, *CONCURRENT ENGINEERING, MATHEMATICAL MODELS, DECISION MAKING, DISTRIBUTED DATA PROCESSING, COMPUTER LOGIC, COMPUTER PROGRAMMING, SYSTEMS ANALYSIS, SUBROUTINES, INDUCTION SYSTEMS, EXECUTIVE ROUTINES.

Subject Categories : Computer Programming and Software
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE