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.validationecoom 2011-
item.contributorGELADE, Wouter-
item.contributorNEVEN, Frank-
item.fullcitationGELADE, Wouter & NEVEN, Frank (2010) Optimizing the Region Algebra is PSPACE-complete. In: INFORMATION PROCESSING LETTERS, 110(16). p. 639-643.-
item.fulltextWith Fulltext-
item.accessRightsClosed Access-
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

Google ScholarTM

Check

Altmetric


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