- 學位論文
利用抽象化及動態學習之布林比對
Boolean Matching with Abstraction and Dynamic Learning
摘要
布林比對問題為判斷給定的兩布林函式，是否可以在經由一些輸入及輸出的排列組合與反向之後，兩函式互為相等。在本篇論文裡面，我們著重在布林比對的計算核心，提供一個完備的比對架構。我們將布林比對問題包裝成可滿足性求解問題，藉由衝突學習及抽象化，快速有效率的排除不可行的比對組合。藉由局部滿足性賦值化簡，我們強化了學習過程並實現顯著的改善。我們的演算法可以容易地整合以特徵值判斷為主的布林比對技術，並採用其技術於我們計算過程的前置步驟。我們的架構能夠處理廣泛的布林比對問題，並且可以適用於未完全定義的布林函式。實驗結果顯示，我們提出的架構能夠處理廣泛及大尺度的布林比對問題。
並列摘要
Boolean matching determines whether two given Boolean functions can be identical to each other under permutation and/or negation of their input and output variables. In this thesis, we focus on the computation kernel of Boolean matching and propose a complete generic framework. We formulate the Boolean matching problem as SAT solving, and effectively prune infeasible matching solutions through conflict-driven learning and abstraction. Partial assignment reduction is applied to strengthen the power of learning. Our approach is capable of being easily integrated with signature-based techniques and applies them as preprocessing for quick search space reduction. Our framework is applicable for general Boolean matching problem, even for incompletely specified functions. The experimental results show the generality and scalability of our framework.
參考文獻
延伸閱讀
- 孫俊斌（2008）。實體模型之平行布林運算〔碩士論文，國立臺灣大學〕。華藝線上圖書館。https://doi.org/10.6342/NTU.2008.01921
- Wu, C. A. (2008). 在電路上實現之布林函數解法器以及它在利用電路重新連線進行邏輯最佳化之應用 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2008.00350
- Wu, J. C. (2016). 藉由格林函數探討變換迭代法與固定點迭代之間的關聯性 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU201610344
- Lee, T. Y. (2017). 考量布林關係於邏輯電路最佳化的研究 [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-0401201816122448
- Wei, L. C. (2014). Efficient Exact and Approximate String Matching Algorithms [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2014.00138