An analysis of fixed-point queries on binary trees

DOI10.1016/0304-3975(91)90048-7MaRDI QIDQ1183571zbMATH OpenOpenAlexFDO

Authors Steven Lindell

Publication date 28 June 1992

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

Full work available at URL https://doi.org/10.1016/0304-3975(91)90048-7

zbMATH Keywords

binary treesfixed-point queries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Relational queries computable in polynomial time
• The expressive power of fixed-point logic with counting
• scientific article; zbMATH DE number 515737
• On fixed-point logic with counting
• Conjunctive queries over trees

Cites work

• Course of mathematical logic. Vol. 1: Relation and logical formula. Translation edited by David Louvish
• Elementary induction on abstract structures
• Fixed-point extensions of first-order logic
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On the Computational Complexity of Algorithms
• Relational queries computable in polynomial time
• Second-order and Inductive Definability on Finite Structures
• Structure and complexity of relational queries

Cited in

(6)

• An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms
• Finite Variable Logics in Descriptive Complexity Theory
• scientific article; zbMATH DE number 1143799 (Why is no real title available?)
• Computing on structures
• Implicit definability and infinitary logic in finite model theory (extended abstract)
• The expressive power of revised Datalog on problems with closure properties

This page was built for publication: An analysis of fixed-point queries on binary trees

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