Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/10916
Title: Optimizing the Region Algebra is PSPACE-complete
Authors: GELADE, Wouter 
NEVEN, Frank 
Issue Date: 2010
Publisher: Elsevier
Source: INFORMATION PROCESSING LETTERS, 110(16). p. 639-643
Abstract: The Region Algebra is a set-at-a-time algebra for querying text regions. We show that satisfiability, inclusion, and equivalence testing of region algebra expressions are PSPACE-complete. This improves upon the previously known NP lower bounds and EXPTIME upper bounds.
Notes: [Neven, Frank] Hasselt Univ, Diepenbeek, Belgium. Transnat Univ Limburg, Sch Informat Technol, Limburg, Belgium. RP Neven, F, Hasselt Univ, Diepenbeek, Belgium. EM wouter.gelade@uhasselt.be - frank.neven@uhasselt.be
Keywords: Computational complexity; Region Algebra; Databases
Document URI: http://hdl.handle.net/1942/10916
ISSN: 0020-0190
e-ISSN: 1872-6119
DOI: 10.1016/j.ipl.2010.05.006
ISI #: 000280205500005
Category: A1
Type: Journal Contribution
Validations: ecoom 2011
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
paper.pdf101.7 kBAdobe PDFView/Open
Show full item record

Page view(s)

54
checked on May 20, 2022

Download(s)

164
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.