Presburger Arithmetic with Unary Predicates is $\Pi^1_1$ Complete

Halpern, Joseph Y.

J. Symbolic Logic, Tome 56 (1991) no. 1, p. 637-642 / Harvested from Project Euclid

Résumé

We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is $\Pi^1_1$ complete. Adding one unary predicate is enough to get $\Pi^1_1$ hardness, while adding more predicates (of any arity) does not make the complexity any worse.

Publié le : 1991-06-14
Classification:

@article{1183743663,
     author = {Halpern, Joseph Y.},
     title = {Presburger Arithmetic with Unary Predicates is $\Pi^1\_1$ Complete},
     journal = {J. Symbolic Logic},
     volume = {56},
     number = {1},
     year = {1991},
     pages = { 637-642},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743663}
}

Halpern, Joseph Y. Presburger Arithmetic with Unary Predicates is $\Pi^1_1$ Complete. J. Symbolic Logic, Tome 56 (1991) no. 1, pp.  637-642. http://gdmltest.u-ga.fr/item/1183743663/