Vladimir Yu. Sazonov  @ NUS Home/Search
Context Related
| botik.ru/rented/logic/pap...congfin.ps botik.ru/rented/ai/Papers...congfin.ps doc.mmu.ac.uk/STAFF/V.Saz...congfin.ps Cached: PS.gz PS PDF Image Update Help From: botik.ru/PSI/AIReC/logic...papers (more) From: botik.ru/PSI/AIReC/Public.ru (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: . We consider some Bounded Set Theories (BST), which are analogues to Bounded Arithmetic. Corresponding provably-recursive operations over sets are characterized in terms of explicit definability and PTIME- or LOGSPACE-computability. We also present some conservativity results and describe a relation between BST, possibly with Anti-Foundation Axiom, and a Logic of Inductive Definitions (LID) and Finite Model Theory. 1. INTRODUCTION The goal of this paper is to outline the present state of... (Update)
Context of citations to this paper: More
.... 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...
.... 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...
Cited by: More
Choiceless Polynomial Time - Andreas Blass Yuri (1997) (Correct)
Fixed-Point Logics, Descriptive Complexity, And Random.. - Atserias (2002) (Correct)
The Descriptive Complexity of the Fixed-Points of Bounded Formulas - Atserias (2000) (Correct)
Active bibliography (related documents): More All
2.8: Δ-Languages for Sets and LOGSPACE Computable Graph.. - Lisitsa, Sazonov (1997) (Correct)
1.9: Bounded Hyperset Theory and Web-like Data Bases - Lisitsa, Sazonov (1997) (Correct)
1.5: A Bounded Set Theory with Anti-Foundation Axiom and Inductive.. - Sazonov (1995) (Correct)
Similar documents based on text: More All
0.3: Linear Ordering on Graphs, Anti-Founded Sets and Polynomial.. - Lisitsa, Sazonov (1998) (Correct)
0.3: Thinking About Binary Trees In An Objectoriented World - Michael Berman Rowan (1996) (Correct)
0.2: Randomized Binary Search Trees - Martínez (1996) (Correct)
Related documents from co-citation: More All
4: Admissible Sets and Structures (context) - Barwise - 1975
4: Elementary induction on abstract structures (context) - Moschovakis - 1974
3: On uniformity within NC - Barrington, Immerman et al. - 1990
BibTeX entry: (Update)
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. http://citeseer.comp.nus.edu.sg/103440.html More
@misc{ yu97bounded,
author = "V. Yu",
title = "On bounded set theory",
text = "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.",
year = "1997",
url = "citeseer.comp.nus.edu.sg/103440.html" }
Citations (may not include all citations):379 The complexity of relational query languages (context) - Vardi - 1982
159 Non-well-founded sets (context) - Aczel - 1988
120 Elementary Induction on Abstract Structures (context) - Moschovakis - 1974
112 Constructivism in Mathematics (context) - Troelstra, van Dalen - 1988
103 Bounded Arithmetic (context) - Buss - 1986
95 Fixed point extensions of first-order logic (context) - Gurevich, Shelah - 1986
63 Admissible sets and structures (context) - Barwise - 1975
63 Towards logic tailored for computational complexity - Gurevich - 1984
61 Descriptive and computationalcomplexity - Immerman - 1989
39 Algebras of feasible functions (context) - Gurevich - 1983
38 The intrinsic computational difficulty of functions (context) - Cobham - 1964
38 Languages which captures complexity classes (context) - Immerman - 1987
32 Existence and feasibility in arithmetic (context) - Parikh - 1971
29 The method of forcing for nondeterministic automata (context) - Szelepcs'enyi - 1987
28 Vicious Circles: On the Mathematics of Nonwellfounded Phenom.. (context) - Barwise, Moss - 1995
21 The fine structure of the constructible hierarchy (context) - Jensen - 1972
19 Formal theories for transfinite iterations of generalized in.. (context) - Feferman - 1970
19 Polynomial computability and recursivity in finite domains (context) - Sazonov - 1980
8 Automata and life (context) - Kolmogorov - 1979
7 Bounded set theory and polynomial computability (context) - Sazonov - 1985
7 Set-theoretic functions for elementary syntax (context) - Gandy - 1974
7 Bounded set theory and inductive definability (context) - Sazonov - 1991
6 Delta-languages for sets and sub-PTIME graph transformers (context) - Sazonov, Yu - 1995
6 A Primitive recursive set theory and AFA: on the logical com.. (context) - Fernando
5 Is SETL a suitable language for parallel programming? -- a t.. (context) - Dahlhaus - 1987
5 Languages of polynomial queries (context) - Livchak - 1982
5 The Set Model For Database and Information Systems (context) - Gilula - 1994
5 Delta-languages for sets and LOGSPACE computable graph trans.. - Sazonov, Yu - 1995
4 The Choice of programming Primitives in SETL-like Languages (context) - Dahlhaus, Makowsky - 1986
3 On feasible numbers - Sazonov - 1995
3 Semantic programming (context) - Goncharov, Ershov et al. - 1986
3 A conservation result concerningbounded theories and the col.. (context) - Buss - 1987
2 A logical approach to the problem "P=NP (context) - Sazonov - 1980
2 Theories for admissible sets (context) - Jager - 1986
2 On polynomial regular codings of hereditarily finite sets (context) - Sazonov - 1993
2 Feasible constructive proofs and the propositional calculus (context) - Cook - 1975
2 On existence of complete predicate calculus in metamathemati.. (context) - Sazonov - 1981
2 Introduction to the theory of inductive definitions (context) - Aczel - 1977
2 Predicatively reducible systems of set theory (context) - Feferman - 1974
1 A bounded set theory with anti-foundation axiom and inductiv.. - Sazonov - 1995
1 the expressive power of program schemas with sets (context) - Stolboushkin - 1990
1 Numberings theory (context) - Ju - 1977
1 Bounded set theory, polynomial computability and \Deltaprogr.. (context) - Sazonov - 1987
1 Hereditarily-finite sets, data bases and polynomial-time com.. (context) - Sazonov - 1993
1 Some conservationresults for fragments of arithmetic (context) - Paris - 1980
Documents on the same site (http://www.botik.ru/PSI/AIReC/logic/bst/papers.html): More
A Bounded Set Theory with Anti-Foundation Axiom and Inductive.. - Sazonov (1995) (Correct)
Linear Ordering on Graphs, Anti-Founded Sets and Polynomial.. - Lisitsa, Sazonov (1998) (Correct)
Δ-Languages for Sets and LOGSPACE Computable Graph.. - Lisitsa, Sazonov (1997) (Correct)
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.