On complexity reduction of Σ1 formulas

Archive for Mathematical Logic 42 (1):45-58 (2003)
  Copy   BIBTEX


. For a fixed q  ℕ and a given Σ1 definition φ, where d is a parameter, we construct a model M of 1 Δ0 + ¬ exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ having no more than q alternations of blocks of quantifiers.



    Upload a copy of this work     Papers currently archived: 76,346

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Role of Quantifier Alternations in Cut Elimination.Philipp Gerhardy - 2005 - Notre Dame Journal of Formal Logic 46 (2):165-171.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.
Deterministic chaos and computational complexity: The case of methodological complexity reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.


Added to PP

9 (#937,492)

6 months
1 (#450,993)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references