کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661664 1633448 2015 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Equilibrium points of an AND–OR tree: Under constraints on probability
ترجمه فارسی عنوان
نقاط تعادل یک درخت AND-OR: تحت محدودیت های احتمالی
کلمات کلیدی
درخت بازی؛ درخت AND-OR؛ درخت OR-AND؛ توزیع یکسان مستقل؛ پیچیدگی محاسباتی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

We consider a depth-first search based algorithm to find the truth value of the root of an AND–OR tree. The cost is measured by the number of leaves probed during the computation. We consider probability distributions on the truth assignments, and restrict the attention to distributions that have the following properties: 1. The inputs come from a product distribution. 2. The output probability (of the root being assigned zero) is some fixed r   such that 0

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 11, November 2015, Pages 1150–1164
نویسندگان
, ,