Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 105-111 |
Number of pages | 7 |
Journal | Theoretical Computer Science |
Volume | 18 |
Issue number | 1 |
DOIs | |
State | Published - Apr 1982 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science