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