お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-11-01 10:25
三値関数を実現するMalbolge命令列の発見のためのSATエンコーディング
安藤 聡酒井正彦坂部俊樹草刈圭一朗西田直樹名大SS2012-37
抄録 (和) Malbolgeは最も難解なプログラミング言語として知られている.低級アセンブリ言語の開発によりMalbolgeのループプログラムの作成が可能になったものの,低級アセンブリ言語には通常のプログラミング言語が持つような演算命令がなく,Malbolge特有の演算を行う命令のみであるため,低級アセンブリ言語でのプログラミングにも困難が伴う.低級アセンブリプログラミングにおいては,目的のプログラムに必要な二引数三値関数を実現するMalbolge特有の演算命令列の発見が求められる.しかしこれまで,そのような命令列を発見するための手法は網羅的な探索に限られており,低級アセンブリプログラミング上の制限となっていた.本稿では,二引数三値関数を実現するMalbolge命令列の発見にSATソルバを利用した手法を提案することで,この問題の解決を試みる.そのため,二引数三値関数を実現するMalbolge命令列を発見する問題を定式化し,その問題のSATエンコーディングを提案する.実験により,既存手法より高速に,かつ,長い命令列が発見できることが分かった. 
(英) Malbolge is known to be one of the most esoteric programming languages. Although it becomes possible to write programs in Malbolge language due to the development of the low-level assembly language, the programming in the low-level assembly language is difficult. This is because the arithmetic instructions of the low-level assembly language are not those of ordinary programming languages, but the same as the ones of Malbolge. To construct a program in low-level assembly language, it is necessary to find instruction sequences of Malbolge that implement binary trit-wise functions. For finding such instruction sequences, however, an inefficient exhaustive search is the only known method, which is one of limitations in developing programs in the low-level assembly language. In this paper, to solve this problem, we propose a method to find instruction sequences of Malbolge that implement binary trit-wise functions, which is more efficient due to the use of state-of-art SAT solvers. We formalize a problem that finds an instruction sequence of Malbolge that implements a given binary trit-wise function,and propose a SAT encoding for this problem. Experiments shows that our method is able to find instruction sequences faster than the existing method and hence essentially longer ones.
キーワード (和) 難解プログラミング言語 / Malbolge / SATエンコーディング / 三値関数 / / / /  
(英) Esoteric programming language / Malbolge / SAT encoding / Trit-wise function / / / /  
文献情報 信学技報, vol. 112, no. 275, SS2012-37, pp. 7-12, 2012年11月.
資料番号 SS2012-37 
発行日 2012-10-25 (SS) 
ISSN Print edition: ISSN 0913-5685    Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード SS2012-37

研究会情報
研究会 SS IPSJ-SE  
開催期間 2012-11-01 - 2012-11-02 
開催地(和) 広島市立大学、講堂 小ホール 
開催地(英) Hiroshima City University 
テーマ(和) ソフトウェアサイエンス、理論 
テーマ(英) Software science, theory 
講演論文情報の詳細
申込み研究会 SS 
会議コード 2012-11-SS-SE 
本文の言語 日本語 
タイトル(和) 三値関数を実現するMalbolge命令列の発見のためのSATエンコーディング 
サブタイトル(和)  
タイトル(英) A SAT Encoding for Finding Operation Sequences of Malbolge that Implement Trit-wise Functions 
サブタイトル(英)  
キーワード(1)(和/英) 難解プログラミング言語 / Esoteric programming language  
キーワード(2)(和/英) Malbolge / Malbolge  
キーワード(3)(和/英) SATエンコーディング / SAT encoding  
キーワード(4)(和/英) 三値関数 / Trit-wise function  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 安藤 聡 / Satoshi Ando / アンドウ サトシ
第1著者 所属(和/英) 名古屋大学 大学院情報科学研究科 (略称: 名大)
Graduate School of Information Science, Nagoya University (略称: Nagoya Univ.)
第2著者 氏名(和/英/ヨミ) 酒井 正彦 / Masahiko Sakai / サカイ マサヒコ
第2著者 所属(和/英) 名古屋大学 大学院情報科学研究科 (略称: 名大)
Graduate School of Information Science, Nagoya University (略称: Nagoya Univ.)
第3著者 氏名(和/英/ヨミ) 坂部 俊樹 / Toshiki Sakabe / サカベ トシキ
第3著者 所属(和/英) 名古屋大学 大学院情報科学研究科 (略称: 名大)
Graduate School of Information Science, Nagoya University (略称: Nagoya Univ.)
第4著者 氏名(和/英/ヨミ) 草刈 圭一朗 / Keiichirou Kusakari / クサカリ ケイイチロウ
第4著者 所属(和/英) 名古屋大学 大学院情報科学研究科 (略称: 名大)
Graduate School of Information Science, Nagoya University (略称: Nagoya Univ.)
第5著者 氏名(和/英/ヨミ) 西田 直樹 / Naoki Nishida / ニシダ ナオキ
第5著者 所属(和/英) 名古屋大学 大学院情報科学研究科 (略称: 名大)
Graduate School of Information Science, Nagoya University (略称: Nagoya Univ.)
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2012-11-01 10:25:00 
発表時間 25分 
申込先研究会 SS 
資料番号 SS2012-37 
巻番号(vol) vol.112 
号番号(no) no.275 
ページ範囲 pp.7-12 
ページ数
発行日 2012-10-25 (SS) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会