TY - JOUR
T1 - The complexity of presburger arithmetic with bounded quantifier alternation depth
AU - Fürer, Martin
N1 - Funding Information:
* This work was supported Swiss National Foundation.
Funding Information:
by the Science Research Council under grant GR/A 80334 and by the
PY - 1982/4
Y1 - 1982/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0001042546&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0001042546&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(82)90115-3
DO - 10.1016/0304-3975(82)90115-3
M3 - Article
AN - SCOPUS:0001042546
SN - 0304-3975
VL - 18
SP - 105
EP - 111
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -