16セグメントディスプレイ上の英字パターンと1-2セグメント木の一斉射撃問題

山下 和也  酒井 充  丸山 博  広瀬 貞樹  

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.12   pp.1427-1435
発行日: 2015/12/01
早期公開日: 2015/08/17
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2015JDP7015
論文種別: 論文
専門分野: 情報・システム基礎
キーワード: 
一斉射撃問題,  セルオートマトン,  セグメントディスプレイ,  

本文: PDF(777.8KB)>>
論文を購入




あらまし: 
一斉射撃問題は,セルオートマトンに関する有名な問題の一つで,1957年頃にMyhillによって提起され,Mooreによって広く知らされた問題である.この一斉射撃問題に対して,MinskyとMcCarthyによって最初の一斉射撃アルゴリズムが示され,Gotoによって最小時間のアルゴリズムが示されている.その後,最小時間アルゴリズムの状態数を減らす研究や,この問題を拡張した問題に関する研究など,多くの研究がなされている.2010年に7セグメントディスプレイ上の数字パターンの一斉射撃問題が提起された.また,これらの問題がセグメント木の一斉射撃問題に帰着できることが示され,一斉射撃アルゴリズムが示された.本論文では,理論的観点からこの問題を拡張し,16セグメントディスプレイ上の英字パターンの一斉射撃問題を提起する.また,これらの問題が1-2セグメント木の一斉射撃問題に帰着できることを示し,一斉射撃アルゴリズムを与える.