Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata

DOI10.1145/2789208zbMath1426.68177arXiv1302.3741OpenAlexW2143473941MaRDI QIDQ3177734

Mihalis Yannakakis, Alistair Stewart, Kousha Etessami

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.3741

zbMATH Keywords

probabilitymodel checking

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations ⋮ Model Checking Temporal Properties of Recursive Probabilistic Programs ⋮ A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes ⋮ Shortest Paths in One-Counter Systems ⋮ Efficient Analysis of Probabilistic Programs with an Unbounded Counter

This page was built for publication: Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata