We study the complexity of the model-checking problem for the branching-time logic CTL~* and the alternating-time temporal logics ATL/ATL~* in one-counter processes and one-counter games respectively. The complexity is determined for all three logics when integer weights are input in unary (non-succinct) and binary (succinct) as well as when the input formula is fixed and is a parameter. Further, we show that deciding the winner in one-counter games with LTL objectives is 2ExpSpace-complete for both succinct and non-succinct games. We show that all the problems considered stay in the same complexity classes when we add quantitative constraints that can compare the current value of the counter with a constant.
展开▼
