Selected publications

• Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
  with Nofar Carmeli.
  Presented at PODS'23.
  
  
• A Simple Algorithm for Consistent Query Answering under Primary Keys
  with Diego Figueira, Anantha Padmanabha and Cristina Sirangelo.
  Presented at ICDT'23.
  
  
• Enumeration for FO Queries over Nowhere Dense Graphs
  with Nicole Schweikardt and Alex Vigny.
  JACM 69(3), 2022. Presented at PODS'18.
  
  
• Tameness and the power of programs over monoids in DA.
  Nathan Grosshans, Pierre McKenzie.
  LMCS 18(3), 2022. Presented at MFCS'17.
  
  
• Enumerating Answers to First-Order Queries Over Databases of Low Degree
  with Arnaud Durand and Nicole Schweikardt.
  LMCS 18(2), 2022. Presented at PODS'14.
  
  
• Projection Views of Register Automata
  with Victor Vianu
  PODS 2020.
  
  
• Order-Invariant First-Order Logic over Hollow Trees
  with Julien Grange.
  CSL 2020.
  
  
• Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates
  with Matthias Niewerth.
  PODS 2018.
  
  
• Constant delay enumeration for FO queries over databases with local bounded expansion
  with Alex Vigny.
  ICDT 2017.
  
  
• Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion
  with Wojtek Kazana.
  LMCS 16(1), 2020. Presented at PODS'13.
  
  
• Bottom-up automata on data trees and vertical XPath
  with Diego Figueira.
  LMCS 13(4), 2017. Presented at STACS'11.
  
  
• Nondeterminism and an abstract formulation of Neciporuk's lower bound method
  with Paul Beame, Nathan Grosshans, Pierre McKenzie.
  ACM ToCT 9(1), 2016.
  
  
• FO2(+1,<.~) on data trees, data tree automata and branching vector addition systems
  with Florent Jacquemard and Jérémie Dimino.
  LMCS 12(2), 2016.
  
  
• Decidable Characterization in FO2(<,+1) and locality of DA
  with Thomas Place.
  Manuscript, 2016.
  
  
• Datalog Rewritings of Regular Path Queries using Views
  with Nadime Francis and Cristina Sirangelo.
  LMCS 11(4), 2015. Presented at ICDT'14.
  
  
• Capturing MSO with one quantifier
  with Anuj Dawar.
  Yurifest 2015.
  
  
• Guarded negation
  with Vince Bárány and Balder ten Cate.
  JACM 62(3), 2015. Presented at ICALP'11.
  
  
• Deciding definability in FO2(<h,<v) on trees
  with Thomas Place.
  LMCS 11(3), 2015. Presented at LICS'10.
  
  
• A glimpse on constant delay enumeration
  Survey presented at STACS'14 (ennoying bugs were corrected since the conference version).
  
  
• Verification of database-driven systems via amalgamation
  with Mikołaj Bojańczyk and Szymon Toruńczyk.
  Manuscript, Presented at PODS'13.
  
  
• Unary negation
  with Balder ten Cate.
  Logical Methods in Computer Science (LMCS) 9(3), 2013. Presented at STACS'11.
  
  
• Enumeration of monadic second-order queries on trees
  with Wojtek Kazana.
  Trans. on Computational Logic (ToCL) 14(4), 2013.
  
  
• Enumerating with constant delay the answers to a query
  Survey presented at ICDT'13 (since the conference version, some ennoying bugs were corrected).
  
  
• Locality of queries definable in invariant first-order logic with arbitrary built-in predicates
  with Matthew Anderson, Dieter van Melkebeek, and Nicole Schweikardt.
  SIAM J. on Computing 41(6), 2012. Presented at ICALP'11.
  
  
• Piecewise testable tree languages
  with Mikołaj Bojańczyk and Howard Straubing.
  Logical Methods in Computer Science (LMCS) 8(3), 2012. Presented at LICS'08.
  
  
• Automata based verification over linearly ordered data domains
  with Szymon Toruńczyk.
  Presented at STACS'11.
  
  
• A decidable characterization of locally testable tree languages
  with Thomas Place.
  Logical Methods in Computer Science (LMCS) 7(4), 2011. Presented at ICALP'09.
  
  
• Two-variable logic on words with data
  with Mikołaj Bojańczyk, Claire David, Anca Muscholl and Thomas Schwentick.
  Trans. on Computational Logic (ToCL) 12(4), 2011. Presented at LICS'06.
  
  
• First-order query evaluation on structures of bounded degree
  with Wojtek Kazana.
  Logical Methods in Computer Science (LMCS) 7(2), 2011.
  
  
• Addition-invariant FO and regularity
  with Nicole Schweikardt.
  Manuscript (presented at LICS'10).
  
  
• Database theory: Query languages
  with Nicole Schweikardt and Thomas Schwentick.
  A chapter in Algorithms and theory of computation handbook, CRC Press, 2010.
  
  
• Tree languages defined in first-order logic with one quantifier alternation
  with Mikołaj Bojańczyk.
  Logical Methods in Computer Science (LMCS) 6(4), 2010. Presented at ICALP'08.
  
  
• Views and Queries: Determinacy and Rewriting
  with Alan Nash and Victor Vianu.
  Trans. on Database Systems (ToDS) 35(3), 2010. Presented at PODS'05 and ICDT'07.
  
  
• XPath, transitive closure logic, and nested tree walking automata
  with Balder ten Cate.
  J. ACM 57(3), 2010. Presented at PODS'08.
  
  
• Regular tree languages definable in FO and FOmod
  with Michael Benedikt.
  Trans. on Computational Logic (ToCL), 11(1), 2009. Presented at STACS'05, the proceeding version contains an important bug, please use the journal version.
  
  
• Future-looking logics on data words and trees
  with Diego Figueira.
  Presented at MFCS'09.
  
  
• Static Analysis of Active XML Systems
  with Serge Abiteboul and Victor Vianu.
  Trans. on Database Sysytems (ToDS), 34(4), 2009. Presented at PODS'08.
  
  
• Two-variable logic on data trees and applications to XML reasoning
  with Mikołaj Bojańczyk, Anca Muscholl, Thomas Schwentick.
  J. ACM 56(3), 2009. Presented at PODS'06.
  
  
• Towards a Characterization of Order-Invariant Queries over Tame Structures
  with Michael Benedikt.
  J. of Symbolic Logic (JSL), 74(1), pp 168-186, 2009. Presented at CSL'05.
  
  
• Complexity of pebble tree-walking automata
  with Mathias Samuelides.
  Presented at FCT'07.
  
  
• Constant-memory validation of streaming XML documents against DTDs
  with Cristina Sirangelo.
  Presented at ICDT'07.
  
  
• Expressive power of pebble automata
  with Mikołaj Bojańczyk, Mathias Samuelides, and Thomas Schwentick.
  Presented at ICALP'06.
  
  
• Complementing deterministic tree-walking automata
  With Anca Muscholl and Mathias Samuelides.
  Information Processing Letters (IPL), 99(1), pp 33-39, 2006.
  
  
• Active Context-Free Games
  with Anca Muscholl and Thomas Schwentick.
  Theory of Computing Systems, 39(1), 2006. Presented at STACS'04.
  
  
• Representing and Querying XML with Incomplete Information
  with Serge Abiteboul and Victor Vianu.
  Trans. on Database Systems (ToDS), 31(1), pp 208-254, 2006. Presented at PODS'01.
  
  
• The Complexity of XML Typing and XPath Query Evaluation
  with Georg Gottlob, Christoph Koch, and Reinhard Pichler.
  J. ACM 52(2), pp 284-335, 2005. Contains all the results presented at PODS'03, plus more.
  
  
• Order independent temporal properties
  with Sandra de Amo and Nicole Bidoit.
  J. of Logic and Computation 14(2), pp 277-298, 2004.
  
  
• Definable Relations and First-Order Query Languages over Strings
  with Michael Benedikt , Leonid Libkin, and Thomas Schwentick.
  J. ACM 50(5), pp 694-751, 2003. Presented at LICS'01 and PODS'01 .
  
  
• Reachability and Connectivity Queries in Constraint Databases
  with Michael Benedikt, Martin Grohe, and Leonid Libkin.
  J. of Computer and System Sciences (JCSS), 66(1), pp 169-206, 2003. Presented at PODS'00.
  
  
• Validating Streaming XML Documents
  with Victor Vianu
  Presented at PODS'02.
  
  
• On first-order topological queries
  with Martin Grohe.
  Trans. on Computational Logic (ToCL), 3(3), pp 336-358, 2002. Presented at LICS'00.
  
  
• When is the evaluation of conjunctive queries tractable ?
  with Martin Grohe and Thomas Schwentick.
  Presented at STOC, 2001.
  
  
• Querying Spatial Databases via Topological Invariants
  with Victor Vianu.
  J. of Computer and System Sciences (JCSS), 61(2), pp 270-301, 2000. Presented at PODS'98.
  
  
• I was also involved in the Dedale project, but I lost track of the relevant publications.