Exact polyhedral reduction and certified computation for credal linguistic models with interval Markov dynamics

Abstract Interval linguistic reports define lower and upper probabilities of semantic events on a continuous state space. A finite family of reported intervals generates an atomic partition that represents all probability constraints exactly and reduces feasibility to a linear program with at most $$4R+3$$ 4 R + 3 probability variables for R elicited intervals. Exact atom-wise utility extrema give an exact finite linear program for lower and upper expectations; when the extrema are computed numerically, a Lipschitz branch-and-bound method returns certified enclosures with a prescribed a posteriori expectation gap. A weighted minimum-slack program repairs inconsistent assessments. For dynamic uncertainty, row-separable interval Markov sets with stagewise-free transition choices admit an exact occupation-flow linearization, giving linear-program formulations for robust utility, dominance, and minimax regret. A Dobrushin-type bound controls perturbation propagation. Numerical experiments include 1,600 certified semantic computations, 20 controlled infeasibility tests, 120 flow-versus-sampling comparisons, 200 narrow-event grid tests, 200 perturbation tests, a scalability study up to 24 criteria and eight periods, and two decision-data applications. Every certified bracket contained its reference solution, with empirical convergence orders from 0.898 to 0.976. With 1,000 sampled transition paths, the sampled worst-case utility remained 0.241 above the exact flow optimum on average, while the flow formulation solved the corresponding problem in 5.5 ms on average.