Journal of Symbolic Logic 56 (2):637 - 642 (1991)
We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is Π 1 1 complete. Adding one unary predicate is enough to get Π 1 1 hardness, while adding more predicates (of any arity) does not make the complexity any worse
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Expansion of a Model of a Weakly o-Minimal Theory by a Family of Unary Predicates.Bektur Sembiuly Baizhanov - 2001 - Journal of Symbolic Logic 66 (3):1382-1414.
Ω1-Like Recursively Saturated Models of Presburger's Arithmetic.Victor Harnik - 1986 - Journal of Symbolic Logic 51 (2):421 - 429.
The Decision Problem for Branching Time Logic.Yuri Gurevich & Saharon Shelah - 1985 - Journal of Symbolic Logic 50 (3):668-681.
Possible-Worlds Semantics for Modal Notions Conceived as Predicates.Volker Halbach, Hannes Leitgeb & Philip Welch - 2003 - Journal of Philosophical Logic 32 (2):179-223.
Presburger Sets and P-Minimal Fields.Raf Cluckers - 2003 - Journal of Symbolic Logic 68 (1):153-162.
On the Completeness of a Certain System of Arithmetic of Whole Numbers in Which Addition Occurs as the Only Operation.Mojżesz Presburger & Dale Jabcquette - 1991 - History and Philosophy of Logic 12 (2):225-233.
On Decidable Extensions of Presburger Arithmetic: From A. Bertrand Numeration Systems to Pisot Numbers.Françoise Point - 2000 - Journal of Symbolic Logic 65 (3):1347-1374.
Added to index2009-01-28
Total downloads9 ( #444,134 of 2,127,010 )
Recent downloads (6 months)1 ( #391,733 of 2,127,010 )
How can I increase my downloads?
There are no threads in this forum
Nothing in this forum yet.