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

DOI10.1016/S0304-3975(98)00312-0zbMath0930.68057OpenAlexW2083347756MaRDI QIDQ1960423

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

bisimulationdescriptive complexitylinear orderinganti-foundation axiombounded set theorycapturing PTIMEstrongly extensional graphs

Mathematics Subject Classification ID

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

Cites Work

• Non-well-founded sets modeled as ideal fixed points
• Fixed-point extensions of first-order logic
• Elementary induction on abstract structures
• Strengthening of the theorems on polynomial queries
• Hereditarily-finite sets, data bases and polynomial-time computability
• Computational logic and proof theory. 5th Kurt Gödel Colloquium, KGC '97. Vienna, Austria. August 25--29, 1997. Proceedings
• \(\Delta\)-languages for sets and LOGSPACE computable graph transformers
• Modal deduction in second-order logic and set theory. II
• Computing with first-order logic
• Infinitary logic and inductive definability over finite structures
• Database theory - ICDT '97. 6th international conference, Delphi, Greece, January 8--10, 1997. Proceedings
• Relational queries computable in polynomial time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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