[OH08] Dan Olteanu and Jiewen Huang. Using OBDDs for efficient query evaluation on probabilistic databases. In *SUM*, volume 5291, 2008. doi:10.1007/978-3-540-87993-0_26. (see pages: 53, 64)

[OH09] Dan Olteanu and Jiewen Huang. Secondary-storage confidence computation for conjunctive queries with inequalities. In *SIGMOD*, 2009. doi:10.1145/1559845.1559887. (see pages: 53, 64)

[OZ15] Dan Olteanu and Jakub Závodnỳ. Size bounds for factorised representations of query results. *TODS*, 40(1), 2015. doi:10.1145/2656335. (see pages: 22, 25)

[PB83] J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. *SIAM Journal on Computing*, 12(4), 1983. doi:10.1137/0212053. (see page: 59)

[PD06] Mihai Pătraşcu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. *SIAM Journal on Computing*, 35(4), 2006. doi:10.1137/S0097539705447256. (see page: 38)

[Pet19] Liat Peterfreund. *The complexity of relational queries over extractions from text*. PhD thesis, Technion, 2019. (see page: 28)

[Pet21] Liat Peterfreund. Grammars for document spanners. In *ICDT*, 2021. doi:10.4230/LIPIcs.ICDT.2021.7. (see pages: 9, 22, 30, and 31)

[PI97] Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. *JCSS*, 55(2), 1997. doi:10.1006/jcss.1997.1520. (see pages: 38, 39)

[Pin86] Jean-Éric Pin. *Varieties of formal languages*. Foundations of Computer Science. Plenum Publishing Corp., New York, 1986. ISBN: 978-0946536122. doi:10.1007/978-1-4613-2215-3. (see page: 46)

[Pin19] Jean-Éric Pin. Mathematical foundations of automata theory. 2019. URL: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf. (see page: 46)

[Pre17] Nicola Prezza. A framework of dynamic data structures for string processing. In *SEA*, 2017. doi:10.4230/LIPIcs.SEA.2017.11. (see page: 37)
[PT07a] Mihai Pătraşcu and Corina E. Tarniţă. On dynamic bit-probe complexity. *Theoretical Computer Science*, 380(1-2), 2007. doi: 10.1016/j.tcs.2007.02.058. (see page: 43)

[PT07b] Mihai Pătraşcu and Mikkel Thorup. Randomization does not help searching predecessors. In *SODA*, volume 7, 2007. URL: http://people.csail.mit.edu/mip/papers/ randpred/randpred.pdf. (see page: 49)

[RD00] Erhard Rahm and Hong Hai Do. Data cleaning: Problems and current approaches. *IEEE Data Eng. Bull.*, 23(4), 2000. URL: http://sites.computerscience.org/debull/A00dec/rahm.ps. (see page: 52)

[Res18] IBM Research. SystemT, 2018. URL: https://researcher.watson.ibm.com/researcher/view_group.php?id=1264. (see page: 28)

[RS07] Christopher Re and Dan Suciu. Materialized views in probabilistic databases: For information exchange and query optimization. *PVLDB*, 2007. URL: https://vldb.org/conf/2007/papers/research/p51-re.pdf. (see page: 52)

[Rus03] Frank Ruskey. *Combinatorial generation*, volume 11. University of Victoria, Victoria, BC, Canada, 2003. Preliminary working draft. URL: https://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf. (see page: 19)

[Sch78] Thomas J. Schaefer. The complexity of satisfiability problems. In *STOC*, 1978. doi:10.1145/800133.804350. (see page: 63)

[SdBBA19] Andy Shih, Guy Van den Broeck, Paul Beame, and Antoine Amarilli. Smoothing structured decomposable circuits. In *NeurIPS*, 2019. URL: https://papers.nips.cc/paper/9318-smoothing-structured-decomposable-circuits. (see page: 24)

[Seg13] Luc Segoufin. Enumerating with constant delay the answers to a query. In *ICDT*, 2013. doi:10.1145/2448496.2448498. (see page: 20)

[Seg14] Luc Segoufin. A glimpse on constant delay enumeration. In *STACS*, 2014. doi:10.4230/LIPIcs.STACS.2014.13. (see page: 20)
[Seg15] Luc Segoufin. Constant delay enumeration for conjunctive queries. *ACM SIGMOD Record*, 44(1), 2015. doi:10.1145/2783888.2783894. (see page: 20)

[SFMS97] Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. *JACM*, 44(2), 1997. doi:10.1145/256303.256309. (see pages: 9, 39, 40, 43, 46, and 48)

[SJMR18] Pierre Senellart, Louis Jachiet, Silviu Maniu, and Yann Ramusat. ProvSQL: Provenance and probability management in PostgreSQL. *PVLDB*, 11(12), 2018. doi:10.14778/3229863.3236253. (see pages: 34, 63)

[SM19] Yann Strozecki and Arnaud Mary. Efficient enumeration of solutions produced by closure operations. *DMTCS*, 21, 2019. doi:10.23638/DMTCS-21-3-22. (see pages: 30, 34)

[SORK11] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic databases. *Synthesis lectures on data management*, 3(2), 2011. ISBN: 978-1608456802. (see pages: 52, 61)

[SS21a] Markus L. Schmid and Nicole Schweikardt. Spanner evaluation over SLP-compressed documents. In *PODS*, 2021. doi:10.1145/3452021.3458325. (see page: 36)

[SS21b] Markus L. Schmid and Nicole Schweikardt. A purely regular approach to non-regular core spanners. In *ICDT*, 2021. doi:10.4230/LIPIcs.ICDT.2021.4. (see page: 35)

[SSV22] Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs. *JACM*, 69(3), 2022. doi:10.1145/3517035. (see pages: 20, 39, and 50)

[Str85] Howard Straubing. Finite semigroup varieties of the form V\*D. *Journal of Pure and Applied Algebra*, 36, 1985. doi:10.1016/0022-4049(85)90062-3. (see page: 47)

[Str19] Yann Strozecki. Enumeration complexity. *Bulletin of EATCS*, 3(129), 2019. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/596/605. (see page: 21)

[SV17] Luc Segoufin and Alexandre Vigny. Constant delay enumeration for FO queries over databases with local bounded expansion. In *ICDT*, 2017. doi:10.4230/LIPIcs.ICDT.2017.20. (see pages: 20, 50)
[SVZ18] Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic complexity under definable changes. *TODS*, 43(3), 2018. doi: 10.1145/3241040. (see page: 49)

[SZ16] Thomas Schwentick and Thomas Zeume. Dynamic complexity: Recent updates. *ACM SIGLOG News*, 3(2), 2016. doi:10.1145/2948896.2948899. (see page: 38)

[TAG+20] Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. Optimal algorithms for ranked enumeration of answers to full conjunctive queries. *PVLDB*, 13(9), 2020. doi:10.14778/3397230.3397250. (see page: 34)

[TIAS77] Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets. *SIAM Journal on Computing*, 6(3), 1977. doi:10.1137/0206036. (see page: 19)

[Tor20] Szymon Toruńczyk. Aggregate queries on sparse databases. In *PODS*, 2020. doi:10.1145/3375395.3387660. (see page: 33)

[TW68] James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. *Mathematical systems theory*, 2(1), 1968. doi:10.1007/BF01691346. (see page: 14)

[Val75] Leslie G. Valiant. General context-free recognition in less than cubic time. *JCSS*, 10(2), 1975. doi:10.1016/S0022-0000(75) 80046-8. (see page: 32)

[Val79] Leslie G. Valiant. The complexity of enumeration and reliability problems. *SIAM Journal on Computing*, 8(3), 1979. doi:10.1137/0208032. (see pages: 19, 52, 58, and 59)

[Val08] Leslie G. Valiant. Holographic algorithms. *SIAM Journal on Computing*, 37(5), 2008. doi:10.1137/070682575. (see page: 63)

[vEBKZ76] Peter van Emde Boas, Robert Kaas, and Erik Zijlstra. Design and implementation of an efficient priority queue. *Mathematical systems theory*, 10(1), 1976. doi:10.1007/BF01683268. (see page: 46)

[Was16] Kunihiro Wasa. Enumeration of enumeration algorithms, 2016. (see page: 19)
[Weg00] Ingo Wegener. *Branching programs and binary decision diagrams*. SIAM, 2000. ISBN: 978-0898714586. (see page: 24)

[WG98] Tim A. Wagner and Susan L. Graham. Efficient and flexible incremental parsing. *TOPLAS*, 20(5), 1998. doi:10.1145/293677.293678. (see pages: 48, 50)

[XZZ07] Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. *Theoretical Computer Science*, 384(1), 2007. doi:10.1016/j.tcs.2007.05.023. (see page: 57)

[Yan81] Mihalis Yannakakis. Algorithms for acyclic database schemes. In *VLDB*, volume 81, 1981. URL: https://dl.acm.org/doi/10.5555/1286831.1286840. (see page: 38)