## 抄録

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 k, all rings of size k or greater exhibit 'similar' behavior. The key concept is the similarity between rings, where rings R^{k} and R^{l} of sizes k and l, respectively, are said to be similar if, intuitively, (1) none of the components in either ring can tell whether it is in R^{k} or R^{l}, and (2) 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: (1) Is there k such that R^{k} and R^{k+1} are similar? (2) Is there k such that all rings of size k or greater are mutually similar? (3) Is there k such that R^{k} is uniform? (4) Is there k such that R^{k}, R^{k+1}, R^{k+2},... are all uniform?

本文言語 | 英語 |
---|---|

ページ（範囲） | 1436-1441 |

ページ数 | 6 |

ジャーナル | Proceedings of the IEEE International Conference on Systems, Man and Cybernetics |

巻 | 2 |

出版ステータス | 出版済み - 1995 |

外部発表 | はい |

イベント | Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5) - Vancouver, BC, Can 継続期間: 10月 22 1995 → 10月 25 1995 |

## !!!All Science Journal Classification (ASJC) codes

- 制御およびシステム工学
- ハードウェアとアーキテクチャ