- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Presburger arithmetic with unary predicates is Π11 complete
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 worseAuthor's Profile
Other Versions
No versions found
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
A note on definability in fragments of arithmetic with free unary predicates.Stanislav O. Speranski - 2013 - Archive for Mathematical Logic 52 (5-6):507-516.
Bounding quantification in parametric expansions of Presburger arithmetic.John Goodrick - 2018 - Archive for Mathematical Logic 57 (5-6):577-591.
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.
Undefinability of Multiplication in Presburger Arithmetic with Sets of Powers.Chris Schulz - forthcoming - Journal of Symbolic Logic:1-15.
Definable groups in models of Presburger Arithmetic.Alf Onshuus & Mariana Vicaría - 2020 - Annals of Pure and Applied Logic 171 (6):102795.
Expansions of Presburger arithmetic with the exchange property.Nathanaël Mariaule - 2021 - Mathematical Logic Quarterly 67 (4):409-419.
Rigid models of Presburger arithmetic.Emil Jeřábek - 2019 - Mathematical Logic Quarterly 65 (1):108-115.
Applications of Strict Π 1 1 Predicates to Infinitary Logic.Jon Barwise - 1974 - Journal of Symbolic Logic 39 (2):335-336.
The Axiom of Choice in Second‐Order Predicate Logic.Christine Gaßner - 1994 - Mathematical Logic Quarterly 40 (4):533-546.
Analytics
Added to PP
2009-01-28
Downloads
75 (#276,337)
6 months
17 (#166,136)
2009-01-28
Downloads
75 (#276,337)
6 months
17 (#166,136)
Historical graph of downloads
Author's Profile
Citations of this work
Notes on the Computational Aspects of Kripke’s Theory of Truth.Stanislav O. Speranski - 2017 - Studia Logica 105 (2):407-429.
A note on definability in fragments of arithmetic with free unary predicates.Stanislav O. Speranski - 2013 - Archive for Mathematical Logic 52 (5-6):507-516.
Sharpening complexity results in quantified probability logic.Stanislav O. Speranski - forthcoming - Logic Journal of the IGPL.
References found in this work
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-f8568656d-snkrx uwo