Corrections to some errors in my papers
Marcelo Arenas, Gonzalo I. Díaz and Egor V. Kostylev. Reverse Engineering SPARQL Queries. In Proceedings of the 25th International Conference on World Wide Web (WWW'16), Montreal, Canada, pages 239-249, 2016.
Table 2: The complexity of the problem
for the query languages SP[AOwd], SP[AOF∧,=,≠wd]
should be 
-complete, instead of coNP-complete. Besides, it is claimed in this table that the complexity of
for the query language SP[AOFwd] is PTIME, but the proof of this claim is incorrect, and we only know at this point that it is in NP.
The aforementioned corrections can be found in Table 3.3 in the PhD thesis of Gonzalo Díaz at the University of Oxford. This thesis includes the complete proofs of all the results in the paper Reverse Engineering SPARQL Queries.
Marcelo Arenas, Gabriel Diéguez and Jorge Pérez. Expressiveness and Complexity of Bidirectional Constraints for Data Exchange. In Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management (AMW'14), Cartagena, Colombia, 2014.
First two lines of Theorem 1: Σ should be a set of full st-tgds with a single atom in its target side, instead of a set of full FO-TO-CQ dependencies with a single atom in its target side. As a consequende of this change, the input of Algorithm 1 BidirectionalMappingFull(M) should be an st-mapping M = (S, T, Σ), where Σ is a set of full st-tgds such that each dependency in Σ has a single atom in its right-hand side.
Carlos Buil-Aranda, Marcelo Arenas, Oscar Corcho and Axel Polleres. Federating Queries in SPARQL1.1: Syntax, Semantics and Evaluation. Journal of Web Semantics 18(1):1-17, 2013.
If P is a graph pattern of the form (GRAPH c
Q) with c in I, then
is defined as
if c does not belong to names(DS) (see Figure 1). This semantics does not agree with
the official
semantics of the GRAPH operator given by the W3C (thanks
to Xiaowang Zhang for pointing this out to us). To solve this problem
has to be defined as
(the empty set of mappings).
Jorge Pérez, Marcelo Arenas and Claudio Gutierrez. Semantics and Complexity of SPARQL. ACM Transactions on Database Systems, 34(3), Article 16 (45 pages), 2009.
The following error was introduced by the journal during the editing/proofing stages. Second line of page 6:
should be replaced by:
Thanks to Andres Letelier for catching this.
Marcelo Arenas, Pablo Barceló and Leonid Libkin. Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07), Wroclaw, Poland, volume 4596 of Lecture Notes in Computer Science, pages 888-900, 2007.
The proof of Theorem 3 (and, thus, of Corollary 7) is incorrect. In the journal version of this paper, we provide a corrected proof of the fact that for every alternating NWA, there exists (and can be effectively constructed) an equivalent NWA. More precisely, the following is proved in the journal version of this paper:
Proposition 4.14. For every alternating NWA of size n, there exists (and can be effectively constructed) an equivalent NWA of size:
Jorge Pérez, Marcelo Arenas and Claudio Gutierrez. Semantics and Complexity of SPARQL. In Proceedings of the 5th International Semantic Web Conference (ISWC'06), Athens, GA, USA, volume 4273 of Lecture Notes in Computer Science, pages 30-43, Springer, 2006.
Point (3) of Proposition 1 is incorrect (thanks to Michael Schmidt for pointing this out to us). It states that the following equivalence holds in general:
As a consequence, the proof that shows that every SPARQL pattern is equivalent to a pattern in UNION normal is not correct. Nevertheless, we provide in the journal version of this paper a new proof of this fact, which does not use the previous incorrect equivalence.
Marcelo Arenas, Leopoldo Bertossi and Michael Kifer. Applications of Annotated Predicate Calculus to Querying Inconsistent Databases. In Proceedings of the 6th International Conference on Rules and Objects in Databases (DOOD'00), London, UK, volume 1861 of Lecture Notes in Artificial Intelligence, pages 926-941. Springer, 2000.
Third line of Proposition 3 (page 940): NP-complete must be replaced by coNP-complete.