Hereditarily-finite sets, data bases and polynomial-time computability

DOI10.1016/0304-3975(93)90345-TzbMath0782.68063OpenAlexW2017735410MaRDI QIDQ1311973

Vladimir Yu. Sazonov

Publication date: 19 January 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90345-t

zbMATH Keywords

resource bounded languageresource bounded programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Related Items (4)

A query language for NC ⋮ \(\Delta\)-languages for sets and LOGSPACE computable graph transformers ⋮ Linear ordering on graphs, anti-founded sets and polynomial time computability ⋮ Structural recursion as a query language on lists and ordered trees

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-point extensions of first-order logic
• On the scheme of induction for bounded arithmetic formulas
• Bounded arithmetic and truth definition
• Foundational studies. Selected works. Vol. I, II
• Computable queries for relational data bases
• The polynomial-time hierarchy
• Structure and complexity of relational queries
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Extended algebra and calculus for nested relational databases
• The collection principle and the existential quantifier
• Turing machines and the spectra of first-order formulas
• Existence and feasibility in arithmetic

This page was built for publication: Hereditarily-finite sets, data bases and polynomial-time computability