کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419912 683876 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extended resolution simulates binary decision diagrams
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Extended resolution simulates binary decision diagrams
چکیده انگلیسی

We prove that binary decision diagrams [R. Bryant, Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Comput. Surveys 23 (3) (1992)] can be polynomially simulated by the extended resolution rule of [G.S. Tseitin, On the complexity of derivation in propositional calculus, in: A. Slisenko (Ed.), Studies in Constructive Mathematics and Mathematical Logics, 1968]. More precisely, for any unsatisfiable formula φφ, there exists an extended resolution refutation of φφ where the number of steps is polynomially bounded by the maximal size of the BDDs built from the formulae occurring in φφ.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 6, 15 March 2008, Pages 825–837
نویسندگان
,