Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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
URI: http://hdl.handle.net/1942/10916
DOI: 10.1016/j.ipl.2010.05.006
ISI #: 000280205500005
ISSN: 0020-0190
Category: A1
Type: Journal Contribution
Validation: ecoom, 2011
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A101.7 kBAdobe PDF

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