Optimizing the region algebra is PSPACE-complete

DOI10.1016/J.IPL.2010.05.006MaRDI QIDQ765502zbMATH OpenOpenAlexFDO

Authors Wouter Gelade, Frank Neven

Publication date 19 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1942/10916

zbMATH Keywords

computational complexitydatabasesregion algebra

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algebras for querying text regions: Expressive power and optimization
• Algebraic Structures with Hard Equivalence and Minimization Problems
• scientific article; zbMATH DE number 1086662
• scientific article; zbMATH DE number 1134629
• scientific article; zbMATH DE number 1515867

Cites work

• Algebras for querying text regions: Expressive power and optimization
• Attribute grammars for unranked trees as a query language for structured documents
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)

Cited in

(1)

• Algebras for querying text regions: Expressive power and optimization

This page was built for publication: Optimizing the region algebra is PSPACE-complete

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