Alexei Lisitsa, Vladimir Sazonov  @ NUS Home/Search
Context Related
| botik.ru/rented/ai/Papers/tcs.ps botik.ru/rented/logic/papers/S...tcs.ps Cached: PS.gz PS PDF Image Update Help From: botik.ru/PSI/AIReC/Public.ru (more) From: botik.ru/PSI/AIReC/logic...papers (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: We discuss several versions of a set theoretic \Delta-language as a reasonable prototype for "nested" data base query language where data base states and queries are considered, respectively, as hereditarily-finite sets and set theoretic operations. In a previous work such a language exactly corresponding to PTIME-computability was introduced. It is supposed that HF-sets are naturally presented by vertices of acyclic graphs. Here we consider a number of languages for Sub-PTIME computable set... (Update)
Context of citations to this paper: More
.... work on characterizing the complexity classes of computable set theoretic operations by some bounded set theory (BST) languages [16] [22]. So, definability in the language Delta D considered in [19, 20] over HFA sets (cf. also the Appendix below) was characterized in terms...
...those vertices of a graph which denote the same 3 The results of Sections 4.2 and 4.3 were obtained in cooperation with A. Lisitsa [44, 45]. cong fin.tex Date: April 26, 1996 Time: 11:26 ON BOUNDED SET THEORY 9 set under collapsing. However, this is hardly possible...
Cited by: More
Complexity and Expressive Power of Logic Programming - Dantsin, Eiter, Gottlob.. (1997) (Correct)
Bounded Hyperset Theory and Web-like Data Bases - Lisitsa, Sazonov (1997) (Correct)
Linear Ordering on Graphs, Anti-Founded Sets and Polynomial.. - Lisitsa, Sazonov (1998) (Correct)
Active bibliography (related documents): More All
2.8: On Bounded Set Theory - Sazonov (1997) (Correct)
0.7: On Linear Ordering of Strongly Extensional Finitely-Branching.. - By Alexei (1997) (Correct)
0.6: A Bounded Set Theory with Anti-Foundation Axiom and Inductive.. - Sazonov (1995) (Correct)
Similar documents based on text: More All
0.3: Implementing Invariant Search via Temporal Resolution - Lisitsa, Brotherston (Correct)
0.2: Temporal Logic With Predicate Lambda-Abstraction. - Lisitsa, Potapov (2005) (Correct)
0.2: Membership and Reachability Problems for Row-monomial.. - Lisitsa, Potapov (2004) (Correct)
Related documents from co-citation: More All
5: Delta-languages for sets and sub-PTIME graph transformers (context) - Sazonov, Yu - 1995
5: Relational queries computable in polynomial time - Immerman - 1986
4: Non-Well-Founded Sets (context) - Aczel - 1987
BibTeX entry: (Update)
Lisitsa, A.P., Sazonov V. Yu.: \Delta-languages for sets and LOGSPACE-computable graph transformers, Theoretical Computer Science, tentatively in Vol. 175, 1997, 42 pp. http://citeseer.comp.nus.edu.sg/225573.html More
@misc{ lisitsa97deltalanguages,
author = "A. Lisitsa and V. Sazonov",
title = "Delta-languages for sets and LOGSPACE-computable graph transformers",
text = "Lisitsa, A.P., Sazonov V. Yu.: \Delta-languages for sets and LOGSPACE-computable
graph transformers, Theoretical Computer Science, tentatively in Vol. 175,
1997, 42 pp.",
year = "1997",
url = "citeseer.comp.nus.edu.sg/225573.html" }
Citations (may not include all citations):4212 Computers and Intractability: A Guide to the Theory of NP-Co.. (context) - Garey, Johnson - 1979
379 The complexity of relational query languages (context) - Vardi - 1982
181 Mathematical Logic (context) - Shoenfield - 1967
159 Non-Well-Founded Sets (context) - Aczel - 1988
157 Efficiently updating materialized view - Blakely, Larson et al. - 1986
103 Bounded Arithmetic (context) - Buss - 1986
61 Descriptive and computational complexity - Immerman - 1989
45 A new approach to database logic (context) - Kuper, Vardi - 1984
39 Algebras of feasible functions (context) - Gurevich - 1983
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
27 The expressiveness of a family of finite set languages - Immerman, Patnaik et al. - 1996
24 Tractable query languages for complex object databases - Grumbach, Vianu - 1991
21 The fine structure of the constructible hierarchy (context) - Jensen - 1972
19 Polynomial computability and recursivity in finite domains (context) - Sazonov - 1980
10 data bases and polynomial-time computability (context) - Sazonov - 1993
7 Bounded set theory and inductive definability (context) - Sazonov - 1991
7 Set theoretic functions for elementary syntax (context) - Gandy - 1974
7 Bounded set theory and polynomial computability (context) - Sazonov - 1985
6 Delta-languages for sets and sub-PTIME graph transformers (context) - Sazonov, Yu - 1995
5 Is SETL a suitable language for parallel programming---a the.. (context) - Dahlhaus - 1987
4 also a short English version of this paper in: Lect (context) - Sazonov - 1987
4 The Choice of programming Primitives in SETL-like Languages (context) - Dahlhaus, Makowsky - 1986
3 Methodology and Philosophy of Sciences (context) - Sazonov - 1995
2 Predicatively reducible systems of set theory (context) - Feferman - 1974
2 On existence of complete predicate calculus in metamathemati.. (context) - Sazonov - 1981
2 On polynomial regular codings of hereditarily finite sets (context) - Sazonov - 1993
2 Raschet i optimizacija teplotehnicheskih ob'ektov s pomosh'j.. (context) - Livchak - 1982
1 Mathematics, Kybernetics (context) - Red'ko, Basarab - 1987
1 Glavnaja redakcija phisicomatematicheskoi literatury (context) - Yu, Numberings et al. - 1977
1 Query languages for hierarhic databases (context) - Dahlhaus, Makowsky - 1992
1 An important correction to this paper is given (context) - Sazonov, Yu et al. - 1980
1 A hierarchy of formulas in set theory (context) - Levy - 1965
1 Primitive recursive set functions (context) - Jensen, Karp - 1971
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.botik.ru/PSI/AIReC/Public.ru.html): More
On Model Checking Complexity of Circumscription (Extended Abstract) - Lisitsa (1999) (Correct)
Linear Ordering on Graphs, Anti-Founded Sets and Polynomial.. - Lisitsa, Sazonov (1998) (Correct)
On Bounded Set Theory - 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.