Graduate studies at Western
Journal of Symbolic Logic 56 (2):637 - 642 (1991)
|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 Π 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)|
|Through your library||Configure|
Similar books and articles
Bektur Sembiuly Baizhanov (2001). Expansion of a Model of a Weakly o-Minimal Theory by a Family of Unary Predicates. Journal of Symbolic Logic 66 (3):1382-1414.
Victor Harnik (1986). Ω1-Like Recursively Saturated Models of Presburger's Arithmetic. Journal of Symbolic Logic 51 (2):421 - 429.
Yuri Gurevich & Saharon Shelah (1985). The Decision Problem for Branching Time Logic. Journal of Symbolic Logic 50 (3):668-681.
Volker Halbach, Hannes Leitgeb & Philip Welch (2003). Possible-Worlds Semantics for Modal Notions Conceived as Predicates. Journal of Philosophical Logic 32 (2):179-223.
Raf Cluckers (2003). Presburger Sets and P-Minimal Fields. Journal of Symbolic Logic 68 (1):153-162.
Mojżesz Presburger & Dale Jabcquette (1991). On the Completeness of a Certain System of Arithmetic of Whole Numbers in Which Addition Occurs as the Only Operation. History and Philosophy of Logic 12 (2):225-233.
Françoise Point (2000). On Decidable Extensions of Presburger Arithmetic: From A. Bertrand Numeration Systems to Pisot Numbers. Journal of Symbolic Logic 65 (3):1347-1374.
Added to index2009-01-28
Total downloads3 ( #213,731 of 739,346 )
Recent downloads (6 months)1 ( #61,538 of 739,346 )
How can I increase my downloads?