کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
463832 697245 2010 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Quasi-Birth–Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
Quasi-Birth–Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems
چکیده انگلیسی

We begin by observing that (discrete-time) Quasi-Birth–Death Processes (QBDs) are equivalent, in a precise sense, to probabilistic 1-Counter Automata (p1CAs), and both Tree-Like QBDs (TL-QBDs) and Tree-Structured QBDs (TS-QBDs) are equivalent to both probabilistic Pushdown Systems (pPDSs) and Recursive Markov Chains (RMCs).We then proceed to exploit these connections to obtain a number of new algorithmic upper and lower bounds for central computational problems about these models. Our main result is this: for an arbitrary QBD, we can approximate its termination probabilities (i.e., its GG matrix) to within ii bits of precision (i.e., within additive error 1/2i1/2i), in time polynomial in both the encoding size of the QBD and in ii, in the unit-cost rational arithmetic RAM model of computation. Specifically, we show that a decomposed Newton’s method can be used to achieve this. We emphasize that this bound is very different from the well-known “linear/quadratic convergence” of numerical analysis, known for QBDs and TL-QBDs, which typically gives no constructive bound in terms of the encoding size of the system being solved. In fact, we observe (based on recent results) that for the more general TL-QBDs such a polynomial upper bound on Newton’s method fails badly. Our upper bound proof for QBDs combines several ingredients: a detailed analysis of the structure of 1-Counter Automata, an iterative application of a classic condition number bound for errors in linear systems, and a very recent constructive bound on the performance of Newton’s method for strongly connected monotone systems of polynomial equations.We show that the quantitative termination decision problem for QBDs (namely, “is Gu,v≥1/2Gu,v≥1/2?”) is at least as hard as long-standing open problems in the complexity of exact numerical computation, specifically the square-root sum problem. On the other hand, it follows from our earlier results for RMCs that any non-trivial approximation of termination probabilities for TL-QBDs is sqrt-root-sum-hard.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Performance Evaluation - Volume 67, Issue 9, September 2010, Pages 837–857
نویسندگان
, , ,