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.

EB00000003250K

Available