On complexity reduction of Σ1 formulas
Archive for Mathematical Logic 42 (1):45-58 (2003)
Abstract
. 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.My notes
Similar books and articles
On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.
Conservative reduction classes of Krom formulas.Stål O. Aanderaa, Egon Börger & Harry R. Lewis - 1982 - Journal of Symbolic Logic 47 (1):110-130.
On the quantifier complexity of Δ n+1 (T)– induction.A. Cordón-Franco, A. Fernández-Margarit & F. F. Lara-Martín - 2004 - Archive for Mathematical Logic 43 (3):371-398.
A reduction class containing formulas with one monadic predicate and one binary function symbol.Charles E. Hughes - 1976 - Journal of Symbolic Logic 41 (1):45-49.
The Role of Quantifier Alternations in Cut Elimination.Philipp Gerhardy - 2005 - Notre Dame Journal of Formal Logic 46 (2):165-171.
Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas.Jarmo Kontinen - 2013 - Studia Logica 101 (2):267-291.
Fitness as default: The evolutionary basis of cognitive complexity reduction.Francis Heylighen - 1994 - In [Book Chapter].
Satisfiability testing for Boolean formulas using δ-trees.G. Gutiérrez, I. P. de Guzmán, J. Martínez, M. Ojeda-Aciego & A. Valverde - 2002 - Studia Logica 72 (1):85 - 112.
Satisfiability Testing for Boolean Formulas Using Δ-Trees.G. Gutiérrez, I. P. De Guzmán, J. Martínez, M. Ojeda-Aciego & A. Valverde - 2002 - Studia Logica 72 (1):85 - 112.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.
After rhetorics of neutrality: Complexity reduction and cultural difference.John I'Anson - 2010 - In Deborah Osberg & Gert Biesta (eds.), Complexity Theory and the Politics of Education. Sense Publishers. pp. 121--34.
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.
The compatibility of complex systems and reduction: A case analysis of memory research. [REVIEW]William Bechtel - 2001 - Minds and Machines 11 (4):483-502.
The reduction of critique in education: Perspectives from Morin's paradigm of complexity.M. Alhadeff-Jones - 2010 - In Deborah Osberg & Gert Biesta (eds.), Complexity Theory and the Politics of Education. Sense Publishers. pp. 25--38.
Analytics
Added to PP
2013-11-23
Downloads
9 (#937,492)
6 months
1 (#450,993)
2013-11-23
Downloads
9 (#937,492)
6 months
1 (#450,993)
Historical graph of downloads
