首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Unique satisfiability of Horn sets can be solved in nearly linear time
Authors:Kenneth A Berman  John Franco  John S Schlipf
Institution:

Department of Computer Science, University of Cincinnati, Cincinnati, OH 45221-0008, USA

Abstract:If a Horn set I has a single satisfying truth assignment or model then that model is said to be unique for I. The question of determining whether a unique model exists for a given Horn set I is shown to be solved in O(greek small letter alpha(L)*L) time, where L is the sum of the lengths of the clauses in I and greek small letter alpha is the inverse Ackermann function. It is also shown that if Lgreater-or-equal, slantedA*log (A) where A is the number of distinct proposition letters then unique satisfiability can be determined in O(L) time.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号