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 |
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.