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