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
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.