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

   
Remote Access
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



Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia