A linear time algorithm for monadic querying of indefinite data over linearly ordered domains

DOI10.1016/S0890-5401(03)00142-1MaRDI QIDQ1887153zbMATH OpenFDO

Authors Mizuhito Ogawa

Publication date 23 November 2004

Published in Information and Computation (Search for Journal in Brave)

zbMATH Keywords

Higman's lemmaQuery answeringLinear-time algorithmWell-quasi-orderingIndefinite data

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• scientific article; zbMATH DE number 2242592
• The complexity of querying indefinite data about linearly ordered domains
• Relational queries computable in polynomial time
• First-order queries on databases embedded in an infinite structure
• scientific article; zbMATH DE number 1406216

Cites work

• scientific article; zbMATH DE number 1678363 (Why is no real title available?)
• scientific article; zbMATH DE number 1301733 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1536573 (Why is no real title available?)
• scientific article; zbMATH DE number 1420905 (Why is no real title available?)
• scientific article; zbMATH DE number 3198033 (Why is no real title available?)
• An improved algorithm for finding tree decompositions of small width
• An intuitionistic proof of Kruskal's theorem
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Nonconstructive tools for proving polynomial-time decidability
• On conjunctive queries containing inequalities
• Ordering by Divisibility in Abstract Algebras
• Ordinal numbers and the Hilbert basis theorem
• Proving termination with multiset orderings
• The complexity of query evaluation in indefinite temporal constraint databases
• The complexity of querying indefinite data about linearly ordered domains
• Well quasi-ordered sets

Cited in

(1)

• scientific article; zbMATH DE number 2242592 (Why is no real title available?)

This page was built for publication: A linear time algorithm for monadic querying of indefinite data over linearly ordered domains

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