Linear ordering on graphs, anti-founded sets and polynomial time computability

DOI10.1016/S0304-3975(98)00312-0MaRDI QIDQ1960423zbMATH OpenOpenAlexFDO

Authors Alexej P. Lisitsa, Vladimir Yu. Sazonov

Publication date 12 January 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(98)00312-0

zbMATH Keywords

anti-foundation axiombisimulationbounded set theorycapturing PTIMEdescriptive complexitylinear orderingstrongly extensional graphs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1114341
• scientific article; zbMATH DE number 4008383
• On computability and tractability for infinite sets
• Infinitary logic and inductive definability over finite structures
• How to define a linear order on finite models

Cites work

• -languages for sets and LOGSPACE computable graph transformers
• Computational logic and proof theory. 5th Kurt Gödel Colloquium, KGC '97. Vienna, Austria. August 25--29, 1997. Proceedings
• Computing with first-order logic
• Database theory - ICDT '97. 6th international conference, Delphi, Greece, January 8--10, 1997. Proceedings
• Elementary induction on abstract structures
• Fixed-point extensions of first-order logic
• Hereditarily-finite sets, data bases and polynomial-time computability
• scientific article; zbMATH DE number 446838 (Why is no real title available?)
• scientific article; zbMATH DE number 3977009 (Why is no real title available?)
• scientific article; zbMATH DE number 4090786 (Why is no real title available?)
• scientific article; zbMATH DE number 4104951 (Why is no real title available?)
• scientific article; zbMATH DE number 3711948 (Why is no real title available?)
• scientific article; zbMATH DE number 42735 (Why is no real title available?)
• scientific article; zbMATH DE number 3494394 (Why is no real title available?)
• scientific article; zbMATH DE number 408791 (Why is no real title available?)
• scientific article; zbMATH DE number 4128804 (Why is no real title available?)
• scientific article; zbMATH DE number 1114341 (Why is no real title available?)
• scientific article; zbMATH DE number 1114351 (Why is no real title available?)
• scientific article; zbMATH DE number 1163985 (Why is no real title available?)
• scientific article; zbMATH DE number 2079051 (Why is no real title available?)
• scientific article; zbMATH DE number 952378 (Why is no real title available?)
• scientific article; zbMATH DE number 4193663 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Infinitary logic and inductive definability over finite structures
• Modal deduction in second-order logic and set theory. II
• Non-well-founded sets modeled as ideal fixed points
• Relational queries computable in polynomial time
• Strengthening of the theorems on polynomial queries

Cited in

(2)

• scientific article; zbMATH DE number 1114341 (Why is no real title available?)
• The Ackermann encoding and its siblings

This page was built for publication: Linear ordering on graphs, anti-founded sets and polynomial time computability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1960423)