Computational complexity of local posteriori inference algorithms in algebraic Bayesian networks

The paper presents algorithmical complexity estimates for local posteriori inference in algebraic Bayesian networks. We consider the ways of implementing the inference for thee types of evidence (deterministic, stochastic, and imprecise). If we need to solve linear programming tasks for inference, the comlexity estimations are given in numbers of such tasks and numbers of variables and constraints in each task. In other cases, complexity estimates are given in numbers of arithmetic operations.