It is shown how the method of Fischer and Rabin can be extended to get good lower bounds for Presburger arithmetic with a bounded number of quantifier alternations. In this case, the complexity is one exponential lower than in the unbounded case. This situation is typical for first order theories.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)