Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Complexity of subcases of Presburger arithmetic
HTML articles powered by AMS MathViewer

by Bruno Scarpellini PDF
Trans. Amer. Math. Soc. 284 (1984), 203-218 Request permission

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
  • Kenneth L. Manders and Leonard Adleman, NP-complete decision problems for binary quadratics, J. Comput. System Sci. 16 (1978), no. 2, 168–184. MR 490916, DOI 10.1016/0022-0000(78)90044-2
    • D. C. Cooper, Theorem proving in arithmetic without multiplication, Machine Intelligence Workshop 7 (1972), 91-100.
  • Jeanne Ferrante and Charles W. Rackoff, The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979. MR 537764
  • Martin Fürer, The complexity of Presburger arithmetic with bounded quantifier alternation depth, Theoret. Comput. Sci. 18 (1982), no. 1, 105–111. MR 650243, DOI 10.1016/0304-3975(82)90115-3
  • Michael J. Fischer and Michael O. Rabin, Super-exponential complexity of Presburger arithmetic, Complexity of computation (Proc. SIAM-AMS Sympos., New York, 1973) SIAM-AMS Proc., Vol. VII, Amer. Math. Soc., Providence, R.I., 1974, pp. 27–41. MR 0366646
    • A. Häussler, Polynomial beschränkte nichtdeterministische Turingmaschinen und die Vollständigkeit des aussagenlogischen Erfüllungsproblems, Lecture Notes in Comput. Sci. 43 (1976), 20-35. J. Heintz, Untere Schranken für die Komplexität logischer Entscheidungs-probleme. Lecture Notes in Comput. Sci. 43 (1976), 127-137.
  • L. Hodes and E. Specker, Lengths of formulas and elimination of quantifiers. I, Contributions to Math. Logic (Colloquium, Hannover, 1966) North-Holland, Amsterdam, 1968, pp. 175–188. MR 0238668
  • Derek C. Oppen, Elementary bounds for Presburger arithmetic, Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York, 1973, pp. 34–37. MR 0416111
    • M. Presburger, Ueber die Vollständigkeit eines gewissen Systems ganzer Zahlen, Comptes Rendus, I. Congrès des Math. des Pays Slaves, Warsaw, 1929, pp. 192-201.
  • C. R. Reddy and D. W. Loveland, Presburger arithmetic with bounded quantifier alternation, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978) ACM, New York, 1978, pp. 320–325. MR 521066
    • M. Sieveking and J. v. z. Gathen, Weitere zum Erfüllungsproblem polynomial äquivalente kombinatorische Aufgaben, Lecture Notes in Comput. Sci. 43 (1976), 49-71.
  • Joachim von zur Gathen and Malte Sieveking, A bound on solutions of linear integer equalities and inequalities, Proc. Amer. Math. Soc. 72 (1978), no. 1, 155–158. MR 500555, DOI 10.1090/S0002-9939-1978-0500555-0
  • J. I. Seiferas, M. J. Fischer, and A. R. Meyer, Refinements of the nondeterministic time and space hierarchies, 14th Annual IEEE Symposium on Switching and Automata Theory (Univ. Iowa, Iowa City, Iowa, 1973) IEEE Comput. Soc., Northridge, Calif., 1973, pp. 130–137. MR 0451861
Similar Articles
Additional Information
  • © Copyright 1984 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 284 (1984), 203-218
  • MSC: Primary 03B25; Secondary 03D15, 03F20, 68Q15
  • DOI: https://doi.org/10.1090/S0002-9947-1984-0742421-9
  • MathSciNet review: 742421