Thursday, February 11, 2016
Speaker: Antonia Lechner
Venue: IST Austria
We consider the complexity of deciding the truth of first-order existential sentences of Presburger arithmetic with divisibility. We show that if such a sentence is satisfiable then the smallest satisfying assignment has size at most exponential in the size of the formula, which implies that the decision problem is in NEXPTIME. Establishing this upper bound requires subtle adaptations to an existing decidability proof of Lipshitz.
A more general family of subsets of Presburger arithmetic with divisibility have been known to be decidable by reduction to the purely existential case. We use one of these subsets to show decidability of the LTL synthesis problem for one-counter automata with integer-valued parameters, where counter values range over the nonnegative integers and counter updates are encoded in binary. This problem asks whether for a given parametric one-counter automaton and LTL formula there exist values for the parameters such that all computations from the initial configuration satisfy the formula. The proof of decidability is by reduction to an intermediary synthesis problem which can be encoded as a formula of a decidable subset of Presburger arithmetic with divisibility. We obtain new upper bounds for all of these problems using the NEXPTIME upper bound for the purely existential subset of Presburger arithmetic with divisibility.