WEKO3
アイテム
2次元オートマトンに対するインクドットの効果
https://ipsj.ixsq.nii.ac.jp/records/32508
https://ipsj.ixsq.nii.ac.jp/records/32508ba6ce2fa-5688-4d23-951b-40f934ead8a4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL92030010.pdf (1.2 MB)
|
Copyright (c) 1992 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1992-11-20 | |||||||
| タイトル | ||||||||
| タイトル | 2次元オートマトンに対するインクドットの効果 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | The Effect of Inkdots for Two - Dimensional Automata | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 山口大学工学部 | ||||||||
| 著者所属 | ||||||||
| 山口大学工学部 | ||||||||
| 著者所属 | ||||||||
| 山口大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science and Systems Engineering Faculty of Engineering, Yamaguchi University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science and Systems Engineering Faculty of Engineering, Yamaguchi University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science and Systems Engineering | ||||||||
| 著者名 |
伊藤暁
× 伊藤暁
|
|||||||
| 著者名(英) |
Akira, Ito
× Akira, Ito
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 最近，決定性と非決定性の領域計算量のクラスが分離するがどうがという未解決問題に関連して，インクドットチューリング機械が導入された．インクドット機械とは入力テープ上に目印としてインクドットを落すことが可能なオフライン型チューリング機械である。本稿では，デジタル図形固有の性質に対する弱い認識機械として，インクドット有限状態機械を導入する．まず最初に，予備的な結果として各種3方向チューリイング機械により2次元インクドット有限オートマトンを模倣するために充分な領域計算量を調べる．次に，2次元インクドット有限オートマトンの基本的な性質を調べる．すなわち，インクドットオートマトンとマーカーオートマトンその他のオートマトンとの関係やインクドットの個数に関する受理能力の階層性である．最後に，2次元インクドット有限オートマトンの連結図形認識可能性の問題を考察する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Recently, related to the open problem whether deterministic and nondeterministic space (especially low-level) complexity classes are separated, inkdot Turing machine was introduced. A inkdot machine is a conventional Turing machine capable to drop a inkdot on the given input tape for a landmark. In this paper, we introduce finite state version of inkdot machine as a weakest recognizer of the inherent properties of digital pictures, rather than Turing machine supplied with a one-dimensional working tape. We firstly investigate the sufficient spaces of thee-way Turing machines to simulate two-dimensional inkdot finite automaton, as preliminary results. Next, we investigate the basic properties of two-dimensinal inkdot automaton, i.e., the relationship of two-dimensional inkdot automata to marker or other two-dimensional automata and the hierarchy based on the number of inkdots. Finally, we investigate the recognizability of connected pictures of two-dimensional inkdot finite machines. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1992, 号 94(1992-AL-030), p. 85-92, 発行日 1992-11-20 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
