Sazonov 1997 Vladimir Sazonov, "On bounded set theory", in "Logic and Scientific Methods", ed. Dalla Chiara et al., Kluwer, 1997. @ NUS Home/Search Document Details and Download
Summary Related Articles Check |
This paper is cited in the following contexts:
The Descriptive Complexity of the Fixed-Points of Bounded Formulas - Atserias (2000) (Correct)
....also called bounded formulas. These are the formulas all of whose quantifiers are of the form (9x 2 y) and (8x 2 y) Sazonov has studied the fixed points of bounded formulas in the context of definability on (V ; 2) rather than in the context of uniform definability on finite structures; see [30] for a survey) It was proved by Atserias and Kolaitis [3] that if the fixedpoints of positive Delta 0 formulas LFP( Delta 0 ) were first order definable on BFR, then P LINH and so P 6= PSPACE. Thus, settling whether LFP( Delta 0 ) collapses is already a difficulty question. Nonetheless, the ....
V. Y. Sazonov. On bounded set theory. In Logic and Scientific Methods, pages 85--103. Kluwer Academic Publishers, 1997.
First-Order Logic vs. Fixed-Point Logic in Finite Set Theory - Atserias, Kolaitis (Correct)
....or iterated least fixed points. Furthermore, no additional first order and second order parameters are allowed in LFP( Delta 0 ) formulas. In a series of papers, Sazonov has studied definability in a variant of LFP( Delta 0 ) on the infinite structure (V ; 2) of all hereditarily finite sets (see [Saz97] for a survey) Here, we study uniform definability in LFP( Delta 0 ) on the collection BFR of all finite structures that are images of the BITstructures BITn = f0; 1; n Gamma 1g; BITn ) under the isomorphism e : V . In particular, we investigate the question: does LFP( Delta 0 ) ....
V. Yu. Sazonov. On bounded set theory. In M.L. Dalla Chiara et al., editor, Logic and Scientific Methods, Volume One of the Tenth ICLMPS, pages 85--103. Kluwer, 1997.
Choiceless Polynomial Time - Andreas Blass Yuri (1997) (4 citations) (Correct)
No context found.
Sazonov 1997 Vladimir Sazonov, "On bounded set theory", in "Logic and Scientific Methods", ed. Dalla Chiara et al., Kluwer, 1997.
Fixed-Point Logics, Descriptive Complexity, And Random.. - Atserias (2002) (Correct)
No context found.
V. Y. Sazonov. On bounded set theory. In Logic and Scientific Methods, pages 85--103. Kluwer Academic Publishers, 1997.
Online articles have much greater impact More about CiteSeer.IST at NUS Add search form to your site Submit documents Feedback
CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.