Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T22:40:26.616Z Has data issue: false hasContentIssue false

Presburger arithmetic with unary predicates is Π11 complete

Published online by Cambridge University Press:  12 March 2014

Joseph Y. Halpern*
Affiliation:
IBM Almaden Research Center, San Jose, California 95120

Abstract

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

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable