WEKO3
アイテム
三値関数を実現するMalbolge命令列の発見のためのSATエンコーディング
http://hdl.handle.net/2237/23558
http://hdl.handle.net/2237/2355872e1f68b-e7e1-44fe-84dd-c861f1f1221d
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2016-02-23 | |||||
タイトル | ||||||
タイトル | 三値関数を実現するMalbolge命令列の発見のためのSATエンコーディング | |||||
言語 | ja | |||||
その他のタイトル | ||||||
その他のタイトル | A SAT Encoding for Finding Operation Sequences of Malbolge that Implement Trit-wise Functions | |||||
言語 | en | |||||
著者 |
安藤, 聡
× 安藤, 聡× 酒井, 正彦× 坂部, 俊樹× 草刈, 圭一朗× 西田, 直樹× ANDO, Satoshi× SAKAI, Masahiko× SAKABE, Toshiki× KUSAKARI, Keiichirou× NISHIDA, Naoki |
|||||
アクセス権 | ||||||
アクセス権 | open access | |||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
権利 | ||||||
言語 | ja | |||||
権利情報 | (c)一般社団法人電子情報通信学会 本文データは学協会の許諾に基づきCiNiiから複製したものである | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 難解プログラミング言語 | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Malbolge | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | SATエンコーディング | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 三値関数 | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Esoteric programming language | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Malbolge | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | SAT encoding | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Trit-wise function | |||||
抄録 | ||||||
内容記述 | Malbolgeは最も難解なプログラミング言語として知られている.低級アセンブリ言語の開発によりMalbolgeのループプログラムの作成が可能になったものの,低級アセンブリ言語には通常のプログラミング言語が持つような演算命令がなく,Malbolge特有の演算を行う命令のみであるため,低級アセンブリ言語でのプログラミングにも困難が伴う.低級アセンブリプログラミングにおいては,目的のプログラムに必要な二引数三値関数を実現するMalbolge特有の演算命令列の発見が求められる.しかしこれまで,そのような命令列を発見するための手法は網羅的な探索に限られており,低級アセンブリプログラミング上の制限となっていた.本稿では,二引数三値関数を実現するMalbolge命令列の発見にSATソルバを利用した手法を提案することで,この問題の解決を試みる.そのため,二引数三値関数を実現するMalbolge命令列を発見する問題を定式化し,その問題のSATエンコーディングを提案する.実験により,既存手法より高速に,かつ,長い命令列が発見できることが分かった. | |||||
言語 | ja | |||||
内容記述タイプ | Abstract | |||||
抄録 | ||||||
内容記述 | 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. | |||||
言語 | en | |||||
内容記述タイプ | Abstract | |||||
内容記述 | ||||||
内容記述 | IEICE Technical Report;SS2012-37 | |||||
言語 | en | |||||
内容記述タイプ | Other | |||||
出版者 | ||||||
言語 | ja | |||||
出版者 | 一般社団法人電子情報通信学会 | |||||
言語 | ||||||
言語 | jpn | |||||
資源タイプ | ||||||
資源タイプresource | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | journal article | |||||
出版タイプ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
関連情報 | ||||||
関連タイプ | isVersionOf | |||||
識別子タイプ | URI | |||||
関連識別子 | http://ci.nii.ac.jp/naid/110009642349/ | |||||
ISSN | ||||||
収録物識別子タイプ | PISSN | |||||
収録物識別子 | 0913-5685 | |||||
書誌情報 |
ja : 電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス 巻 112, 号 275, p. 7-12, 発行日 2012-10 |
|||||
著者版フラグ | ||||||
値 | publisher | |||||
シリーズ | ||||||
関連名称 | IEICE Technical Report;SS2012-37 | |||||
URI | ||||||
識別子 | http://ci.nii.ac.jp/naid/110009642349/ | |||||
識別子タイプ | URI | |||||
URI | ||||||
識別子 | http://hdl.handle.net/2237/23558 | |||||
識別子タイプ | HDL |