Selected publications
- 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.
Back to Luc Segoufin's home page.