Corrigendum: CORRIGENDUM: Volume 58, Number 3 (1999), in Article No. “On the Decidability of Semilinearity for Semialgebraic Sets and Its Implications for Spatial Databases,” by Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, and Dirk Van Gucht, pages 535–571

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 127 KB
• Volume: 59
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1696

✦ Synopsis

Unfortunately only after the article went to press, the authors discovered a serious error in Section 5, for which they apologize. The error does not affect results in other sections. Moreover, with only minor modifications, the major results of Section 5 still hold, although several of the proofs that were given are incorrect. Below, the nature of the error is specified and how Section 5 has to be modified is indicated. The correctness of Propositions 5.7 and 5.13 as stated and proved below is especially crucial, as these results are the basis of other previously presented results [1], as well as some other recent, hitherto unpublished results [2].

The error involves Algorithm 5.4 on p. 554. Given a semilinear set S, Algorithm 5.4, implementable in FO+linear-Z, computes sets (called ``layers'') the connected components of which constitute the so-called algorithmic decomposition of S relative to S. Most of the proofs in Section 5 hinge on the correctness of Proposition 5.7, also on p. 554, which, unfortunately, is not true, as shown by the following counterexample.