The complexity of presburger arithmetic with bounded quantifier alternation depth

Martin Fürer

doi:10.1016/0304-3975(82)90115-3

The complexity of presburger arithmetic with bounded quantifier alternation depth

Martin Fürer

Eberly College of Science

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

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	https://doi.org/10.1016/0304-3975(82)90115-3
State	Published - Apr 1982

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(82)90115-3

Cite this

@article{ecf76bc9ea5a408da1f443131be87f54,

title = "The complexity of presburger arithmetic with bounded quantifier alternation depth",

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.",

author = "Martin F{\"u}rer",

note = "Funding Information: * This work was supported Swiss National Foundation. Funding Information: by the Science Research Council under grant GR/A 80334 and by the",

year = "1982",

month = apr,

doi = "10.1016/0304-3975(82)90115-3",

language = "English (US)",

volume = "18",

pages = "105--111",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

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 -

The complexity of presburger arithmetic with bounded quantifier alternation depth

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this