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)

104
checked on Jul 31, 2023

Download(s)

238
checked on Jul 31, 2023

Google ScholarTM

Check

Altmetric


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