| 題名 | ビルディングパズルの計算複雑さ |
| 著者 | *松井 勇太, 岩本 宙造 (広島大学大学院工学研究科情報工学専攻) |
| キーワード | ビルディングパズル, ペンシルパズル, NP完全 |
| アブストラクト | ビルディングパズルは矢印の方向から数字の数だけビルが見えるように高さの違うビルを並べるパズルである. 高いビルが手前にくると低いビルは見えなくなる.N*Nサイズの盤面で一番大きい数字（一番高いビル）はNである。行と列にはマスの数だけ違う高さのビルが存在するので、行と列で各数字はそれぞれ一度ずつ使われる. 以上のルールを用いて,与えられた問題から解を導き出すことがこのゲームの目的である. 本稿ではビルディングパズルのNP完全性を示す. |
| 題名 | GLL構文解析法視覚化ツールの開発 |
| 著者 | *河口 雄大, 伊藤 暁 (山口大学大学院理工学研究科) |
| キーワード | 構文解析 |
| アブストラクト | GLL 構文解析法とは，文法の非決定的な部分に対して複数のプロセスを並列的に作動させ，解析に必要なデータを一つのグラフ状スタックに格納しながら解析を行う構文解析法である[1]．本研究では, 文法遷移図, その文法遷移図上におけるGLL 構文解析法の全動作点の遷移軌跡図，グラフ状スタック図の３点を用いてGLL 構文解析法を直感的にわかりやすくするための視覚化を提案し，それらの視覚化されたGLL 構文解析器を実装する. |
| 題名 | コピー回数限定パターン文脈自由文法 |
| 著者 | *河野 陽太, 玉木 秀磨 (山口大学工学部), 伊藤 暁 (山口大学大学院理工学研究科) |
| キーワード | 文脈自由文法, 拡張正規表現 |
| アブストラクト | パターン表現(pattern expression) はregex 等における後方 参照(back reference) の機能を形式化するために導入された 拡張正規表現である[1, 2]．パターン文脈自由文法(pattern context-free grammar) はパターン表現の考え方を文脈自由 文法に対して導入したものである[3]． 本研究では，まず線形文法と正規文法にコピー機能を持 たせた場合には，言語生成能力は向上しないことを示す． また，パターン表現をそれと等価なパターンCFG に変換す る手法を示す．最後に，パターン表現言語に対する反復補 題を紹介し，その適応例を挙げた後に，コピー回数が1 回 であるようなパターン文脈自由文法に対する反復補題を証 明する． |
| 題名 | 3次元Larger than Life セルオートマトンにおけるバグの探索 |
| 著者 | *久保田 智大 (広島大学大学院工学研究科情報工学専攻), 今井 克暢 (広島大学大学院工学研究院) |
| キーワード | セルオートマトン, ライフゲーム |
| アブストラクト | セルオートマトンとは，空間上に一様に並んだセルと簡単な規則による、離散的計算モデルである。2次元セルオートマトンのルールの一つであるLarger than Life(LtL)は5つのパラメータで表され、その値により非常に多様なパターンを持つ。LtLにはバグと呼ばれる特別な移動パターンが存在する。本研究は3次元に拡張したLtLにおいて、バグが生成される条件を満たすパラメータの範囲を探索し、新たなバグを発見した。 |
| 題名 | 全称状態のみの1方向交代性マルチプロセッサ有限オートマトン |
| 著者 | *久本 純樹 (徳山工業高等専門学校情報電子工学専攻), 義永 常宏 (徳山工業高等専門学校情報電子工学科), 坂本 眞人 (宮崎大学工学部) |
| キーワード | マルチプロセッサ有限オートマトン, 交代性計算, 1方向計算, 全称状態 |
| アブストラクト | マルチプロセッサ有限オートマトン(MPFA)は, 複数の有限オートマトンとスイッチング関数により構成されており, 最も単純な並列計算モデルの1つと考えることができる.これまでにMPFAにおける決定性および非決定性計算についての研究がなされているが, 交代性計算についてはほとんど考察されていない. 本研究では全称状態だけに制限された1方向交代性MPFAの基本的な性質について考察し, �．廛蹈札奪疑瑤亡陲鼎�受理能力の階層性が存在すること, �∩款両�態のみの交代性は決定性よりも真に受理能力が高いこと, �Ｈ鷏萃蠕�と全称状態のみの交代性の受理能力は比較不能であることを示している. また, 関連する未解決問題を提示している. |