Autark assignments of Horn CNFs

作者：Kimura Kei^*; Makino Kazuhisa

来源：Japan Journal of Industrial and Applied Mathematics, 2018, 35(1): 297-309.

DOI：10.1007/s13160-017-0284-6

• Boolean satisfiability problem
• Autark assignment
• Horn CNF
• Combinatorial algorithm

In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs.

• 出版日期2018-3