Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Complexity of subcases of Presburger arithmetic


Author: Bruno Scarpellini
Journal: Trans. Amer. Math. Soc. 284 (1984), 203-218
MSC: Primary 03B25; Secondary 03D15, 03F20, 68Q15
MathSciNet review: 742421
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider formula subclasses of Presburger arithmetic which have a simple structure in one sense or the other and investigate their computational complexity. We also prove some results on the lower bounds of lengths of formulas which are related to questions on quantifier elimination.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03B25, 03D15, 03F20, 68Q15

Retrieve articles in all journals with MSC: 03B25, 03D15, 03F20, 68Q15


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1984-0742421-9
PII: S 0002-9947(1984)0742421-9
Keywords: Presburger arithmetic, complexity of decidable theories, complexity of formulas, lower bounds for lengths of formulas, NP-hard problems, quantifier elimination
Article copyright: © Copyright 1984 American Mathematical Society