Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/10916
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGELADE, Wouter-
dc.contributor.authorNEVEN, Frank-
dc.date.accessioned2010-05-18T11:38:12Z-
dc.date.availableNO_RESTRICTION-
dc.date.issued2010-
dc.identifier.citationINFORMATION PROCESSING LETTERS, 110(16). p. 639-643-
dc.identifier.issn0020-0190-
dc.identifier.urihttp://hdl.handle.net/1942/10916-
dc.description.abstractThe 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.-
dc.description.sponsorshipEuropean Commission [FP7-ICT-233599]; [FWO-G.0821.09N] FX We acknowledge the financial support of FWO-G.0821.09N and the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under the FET-Open grant agreement FOX, number FP7-ICT-233599.-
dc.language.isoen-
dc.publisherElsevier-
dc.subject.otherComputational complexity; Region Algebra; Databases-
dc.titleOptimizing the Region Algebra is PSPACE-complete-
dc.typeJournal Contribution-
local.bibliographicCitation.authors-
dc.identifier.epage643-
dc.identifier.issue16-
dc.identifier.spage639-
dc.identifier.volume110-
local.bibliographicCitation.jcatA1-
dc.description.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-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1016/j.ipl.2010.05.006-
dc.identifier.isi000280205500005-
item.accessRightsOpen Access-
item.fullcitationGELADE, Wouter & NEVEN, Frank (2010) Optimizing the Region Algebra is PSPACE-complete. In: INFORMATION PROCESSING LETTERS, 110(16). p. 639-643.-
item.contributorGELADE, Wouter-
item.contributorNEVEN, Frank-
item.fulltextWith Fulltext-
item.validationecoom 2011-
crisitem.journal.issn0020-0190-
crisitem.journal.eissn1872-6119-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
paper.pdf101.7 kBAdobe PDFView/Open
Show simple 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.