کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9657821 690045 2005 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A hierarchy result for read-once branching programs with restricted parity nondeterminism
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A hierarchy result for read-once branching programs with restricted parity nondeterminism
چکیده انگلیسی
Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (⊕,k)-branching programs and (∨,k)-branching programs are considered, i.e., branching programs starting with a ⊕- (or ∨-)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (⊕,k)- and (∨,k)-branching programs with respect to k are presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 340, Issue 3, 31 August 2005, Pages 594-605
نویسندگان
, ,