Linear Ordering on Graphs, Anti-Founded Sets and Polynomial Time Computability (1998)  (Make Corrections)  
Alexei Lisitsa, Vladimir Sazonov

 @ NUS   Home/Search   Context   Related

 
View or download:
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  
(Enter summary)

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.