Alexei Lisitsa, Vladimir Sazonov  @ NUS Home/Search
Context
Related
| botik.ru/rented/logic/pap...tcs98lo.ps botik.ru/rented/ai/Papers...tcs98lo.ps doc.mmu.ac.uk/STAFF/V.Saz...tcs98lo.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: It is proved definability in FO+IFP of a global linear ordering on vertices of strongly extensional (SE) finitely-branching graphs. In the case of finite SE graphs this also holds for FO+LFP. This gives capturing results for PTIME computability on the latter class of graphs by FO+LFP and FO+IFP, and also on the corresponding anti-founded universe HFA of hereditarily-finite sets by a language \Delta of a bounded set theory BSTA. Oracle PTIME computability over HFA is also captured by an... (Update)
Active bibliography (related documents): More All
2.1: On Linear Ordering of Strongly Extensional Finitely-Branching.. - By Alexei (1997) (Correct)
2.0: Bounded Hyperset Theory and Web-like Data Bases - Lisitsa, Sazonov (1997) (Correct)
1.5: Δ-Languages for Sets and LOGSPACE Computable Graph.. - Lisitsa, Sazonov (1997) (Correct)
Similar documents based on text: More All
0.4: A Bounded Set Theory with Anti-Foundation Axiom and Inductive.. - Sazonov (1995) (Correct)
0.4: A Construction of typed lambda models related to feasible.. - Sazonov (1998) (Correct)
0.4: On the Model Checking Complexity of Circumscription (Extended.. - Lisitsa (Correct)
BibTeX entry: (Update)
@misc{ lisitsa-linear,
author = "Alexei Lisitsa and Vladimir Sazonov",
title = "Linear Ordering on Graphs, Anti-Founded Sets and Polynomial Time Computability",
url = "citeseer.comp.nus.edu.sg/108641.html" }
Citations (may not include all citations):379 Complexity of relational query languages (context) - Vardi - 1982
331 A query Language and Optimization Techniques for Unstructure.. - Buneman, Davidson et al. - 1996
245 Relational queries computable in polynomial time - Immerman - 1982
245 Relational queries computable in polynomial time - Immerman - 1986
159 Non-Well-Founded Sets (context) - Aczel - 1988
120 Elementary Induction on Abstract Structures (context) - Moschovakis - 1974
114 Generic computations and its complexity (context) - Abiteboul, Vianu - 1991
95 Fixed-point extensions of first-order logic (context) - Gurevich, Shelah - 1986
63 Admissible Sets and Structures (context) - Barwise - 1975
57 Infinitary Logic and Inductive Definability over Finite Stru.. - Dawar, Lindell et al. - 1995
43 Computing with First-Order Logic - Abiteboul, Vianu - 1995
38 The intrinsic computational difficulty of function (context) - Cobham
19 Polynomial computability and recursivity in finite domains (context) - Yu - 1980
15 Non-Well-Founded Sets Modeled as Ideal Fixed Points (context) - Mislove, Moss et al. - 1991
13 Modal Deduction in Second-Order Logic and Set Theory - II - van Benthem, Montanari et al. - 1996
10 Observational properties of databases with object identity (context) - Kosky - 1995
10 data bases and polynomial-time computability (context) - Yu, Hereditarily-finite - 1993
8 Bounded Hyperset Theory and Web-like Data Bases - Lisitsa, Yu - 1997
7 Bounded set theory and inductive definability (context) - Yu - 1991
7 Bounded Set Theory and Polynomial Computability (context) - Yu - 1985
6 on Foundations of Computer Science (context) - Gurevich, feasible et al. - 1983
6 Delta-languages for sets and sub-PTIME graph transformers (context) - Yu, Lisitsa - 1995
6 A Primitive Recursive Set Theory and AFA: On Logical Complex.. (context) - Fernando
5 Is SETL a suitable language for parallel programming (context) - Dahlhaus - 1987
5 Delta-languages for sets and LOGSPACEcomputable graph transf.. - Lisitsa, Yu - 1997
5 Capturing Bisimulation-Invariant PTIME (context) - Otto - 1997
5 Vicious Circles: on the mathematics of circular phenomena (context) - Barwise, Moss - 1996
5 North-Holland Publishing Company (context) - Kuratovski, Mostowski et al. - 1967
4 Finite variable logics - Hodkinson - 1993
4 also a short English version of this paper in: Lect (context) - Yu, Bounded et al. - 1987
3 Database Theory -- ICDT (context) - Abiteboul, Vianu et al. - 1997
2 Raschet i optimizacija teplotehnicheskih ob'ektov s pomosh'j.. (context) - Livchak, polynomial - 1982
2 On Substitutional Recursion over Non-Well-Founded Sets (context) - Fernando - 1989
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)
On Bounded Set Theory - Sazonov (1997) (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.