References

[AHV95] Serge Abiteboul, Richard Hull, Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. ISBN 0-201-53771-0. [1] [2]
[AVV97] Serge Abiteboul, Moshe Y. Vardi, Victor Vianu. Fixpoint logics, relational machines, and computational complexity. J. ACM, 44(1):30–56, 1997. doi:10.1145/256292.256295. [1] [2] [3] [4] [5]
[AV89] Serge Abiteboul, Victor Vianu. Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. In Proceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS '89), Pacific Grove, California, USA, June 5-8, 1989, 71–79. IEEE Computer Society, 1989. doi:10.1109/LICS.1989.39160. [1] [2] [3] [4] [5] [6] [7] [8]
[AV91] Serge Abiteboul, Victor Vianu. Generic Computation and Its Complexity. Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC '91), New Orleans, Louisiana, USA, May 5-8, 1991, pages 209–219, 1991. doi:10.1145/103418.103444. [1] [2] [3]
[Ajt83] Miklós Ajtai. $\Sigma^1_1$-formulae on finite structures. Ann. Pure Appl. Log., 24(1):1–48, 1983. doi:10.1016/0168-0072(83)90038-6. [1] [2]
[APT79] Bengt Aspvall, Michael F. Plass, Robert Endre Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Inf. Process. Lett., 8(3):121–123, 1979. doi:10.1016/0020-0190(79)90002-4. [1] [2] [3] [4]
[Bab16] László Babai. Graph isomorphism in quasipolynomial time. In Daniel Wichs, Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 684–697. ACM, 2016. doi:10.1145/2897518.2897542. [1] [2]
[BIS90] David A. Mix Barrington, Neil Immerman, Howard Straubing. On Uniformity within NC$^1$. J. Comput. Syst. Sci., 41(3):274–306, 1990. doi:10.1016/0022-0000(90)90022-D. [1] [2] [3] [4] [5]
[BGG97] Egon Börger, Erich Grädel, Yuri Gurevich. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, 1997. [1]
[CKS81] Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114–133, 1981. doi:10.1145/322234.322243. [1] [2] [3] [4] [5] [6] [7] [8]
[CM77] Ashok K. Chandra, Philip M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In John E. Hopcroft, Emily P. Friedman, Michael A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, 77–90. ACM, 1977. doi:10.1145/800105.803397. [1] [2] [3]
[Coo71] Stephen A. Cook. The Complexity of Theorem-Proving Procedures. In Michael A. Harrison, Ranan B. Banerji, Jeffrey D. Ullman, editors, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, 151–158. ACM, 1971. doi:10.1145/800157.805047. [1] [2] [3] [4] [5] [6] [7] [8]
[Dah83] Elias Dahlhaus. Reduction to NP-complete problems by interpretations. In Egon Börger, Gisbert Hasenjaeger, Dieter Rödding, editors, Logic and Machines: Decision Problems and Complexity, Proceedings of the Symposium "Rekursive Kombinatorik" held from May 23-28, 1983 at the Institut für Mathematische Logik und Grundlagenforschung der Universität Münster/Westfalen, volume 171 of Lecture Notes in Computer Science, 357–365. Springer, 1983. doi:10.1007/3-540-13331-3_51. [1] [2] [3]
[DDLW98] Anuj Dawar, Kees Doets, Steven Lindell, Scott Weinstein. Elementary Properties of the Finite Ranks. Math. Log. Q., 44(3):349–353, 1998. doi:10.1002/malq.19980440306. [1] [2]
[DLW95] Anuj Dawar, Steven Lindell, Scott Weinstein. Infinitary Logic and Inductive Definability over Finite Structures. Inf. Comput., 119(2):160–175, 1995. doi:10.1006/INCO.1995.1084. [1] [2] [3] [4] [5]
[DG84] William F. Dowling, Jean H. Gallier. Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. J. Log. Program., 1(3):267–284, 1984. doi:10.1016/0743-1066(84)90014-1. [1] [2]
[EF95] Heinz-Dieter Ebbinghaus, Jörg Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer, 1995. ISBN 3-540-60149-X. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
[Ehr61] Andrzej Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fundamenta Mathematicae, 49:129–141, 1961. doi:10.4064/fm-49-2-129-141. [1] [2] [3] [4]
[Fag74] Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Richard M. Karp, editor, Complexity of Computation, volume 7 of SIAM-AMS Proceedings, pages 43–73. American Mathematical Society, 1974. [1] [2] [3] [4]
[Fur83] Martin Fürer. The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). In Egon Börger, Gisbert Hasenjaeger, Dieter Rödding, editors, Logic and Machines: Decision Problems and Complexity, Proceedings of the Symposium "Rekursive Kombinatorik" held from May 23-28, 1983 at the Institut für Mathematische Logik und Grundlagenforschung der Universität Münster/Westfalen, volume 171 of Lecture Notes in Computer Science, 312–319. Springer, 1983. doi:10.1007/3-540-13331-3_48. [1] [2] [3]
[FSS84] Merrick L. Furst, James B. Saxe, Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory, 17(1):13–27, 1984. doi:10.1007/BF01744431. [1] [2] [3]
[GW83] Hana Galperin, Avi Wigderson. Succinct Representations of Graphs. Inf. Control., 56(3):183–198, 1983. doi:10.1016/S0019-9958(83)80004-7. [1] [2] [3]
[GMS26] Antoine Gauquier, Ioana Manolescu, Pierre Senellart. Efficient Crawling for Scalable Web Data Acquisition. In Proceedings of the 29th International Conference on Extending Database Technology, EDBT 2026, Tampere, Finland, March 24-27, 2026. 2026. doi:10.48786/edbt.2026.30. [1] [2] [3] [4] [5] [6]
[Gra92] Erich Grädel. Capturing Complexity Classes by Fragments of Second-Order Logic. Theor. Comput. Sci., 101(1):35–57, 1992. doi:10.1016/0304-3975(92)90149-A. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]
[GS86] Yuri Gurevich, Saharon Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265–280, 1986. doi:10.1016/0168-0072(86)90055-2. [1] [2] [3]
[Has86] Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, Berkeley, California, USA, 6–20. ACM, 1986. doi:10.1145/12130.12132. [1] [2] [3] [4]
[HT06] Lauri Hella, José Marı́a Turull Torres. Computing queries with higher-order logics. Theor. Comput. Sci., 355(2):197–214, 2006. doi:10.1016/J.TCS.2006.01.009. [1] [2] [3]
[Hen50] Leon Henkin. Completeness in the Theory of Types. J. Symb. Log., 15(2):81–91, 1950. doi:10.2307/2266967. [1] [2] [3] [4] [5] [6]
[Imm86] Neil Immerman. Relational Queries Computable in Polynomial Time. Inf. Control., 68(1-3):86–104, 1986. doi:10.1016/S0019-9958(86)80029-8. [1] [2] [3] [4]
[Imm87] Neil Immerman. Languages that Capture Complexity Classes. SIAM J. Comput., 16(4):760–778, 1987. doi:10.1137/0216051. [1] [2] [3] [4] [5] [6] [7]
[Imm88] Neil Immerman. Nondeterministic Space is Closed Under Complementation. SIAM J. Comput., 17(5):935–938, 1988. doi:10.1137/0217058. [1] [2] [3] [4]
[Imm99] Neil Immerman. Descriptive Complexity. Graduate Texts in Computer Science. Springer, 1999. ISBN 978-1-4612-6809-3. doi:10.1007/978-1-4612-0539-5. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32]
[Jon75] Neil D. Jones. Space-Bounded Reducibility among Combinatorial Problems. J. Comput. Syst. Sci., 11(1):68–85, 1975. doi:10.1016/S0022-0000(75)80050-X. [1] [2] [3]
[Kar72] Richard M. Karp. Reducibility Among Combinatorial Problems. In Raymond E. Miller, James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972. doi:10.1007/978-1-4684-2001-2_9. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
[KST93] Johannes Köbler, Uwe Schöning, Jacobo Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, 1993. doi:10.1007/978-1-4612-0333-9. [1] [2]
[Lad75] Richard E. Ladner. The Circuit Value Problem is Log Space Complete for P. SIGACT News, 7(1):18–20, 1975. doi:10.1145/990518.990519. [1] [2] [3] [4]
[Lei89] Daniel Leivant. Descriptive Characterizations of Computational Complexity. J. Comput. Syst. Sci., 39(1):51–83, 1989. doi:10.1016/0022-0000(89)90019-6. [1] [2] [3]
[Lev73] Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):265–266, 1973. Russian original: Problemy Peredachi Informatsii 9(3):115–116. [1] [2] [3] [4] [5] [6] [7] [8]
[Lew80] Harry R. Lewis. Complexity Results for Classes of Quantificational Formulas. J. Comput. Syst. Sci., 21(3):317–353, 1980. doi:10.1016/0022-0000(80)90027-6. [1] [2]
[Lib04] Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. ISBN 3-540-21202-7. doi:10.1007/978-3-662-07003-1. [1]
[PY84] Christos H. Papadimitriou, Mihalis Yannakakis. The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci., 28(2):244–259, 1984. doi:10.1016/0022-0000(84)90068-0. [1] [2] [3] [4] [5] [6] [7] [8]
[PY86] Christos H. Papadimitriou, Mihalis Yannakakis. A Note on Succinct Representations of Graphs. Inf. Control., 71(3):181–185, 1986. doi:10.1016/S0019-9958(86)80009-2. [1] [2] [3]
[Pos46] Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264–268, 1946. doi:10.1090/S0002-9904-1946-08555-9. [1] [2] [3]
[Ruz81] Walter L. Ruzzo. On Uniform Circuit Complexity. J. Comput. Syst. Sci., 22(3):365–383, 1981. doi:10.1016/0022-0000(81)90038-6. [1] [2]
[Sav70] Walter J. Savitch. Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci., 4(2):177–192, 1970. doi:10.1016/S0022-0000(70)80006-X. [1] [2] [3]
[Sch78] Thomas J. Schaefer. The Complexity of Satisfiability Problems. In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, 216–226. ACM, 1978. doi:10.1145/800133.804350. [1] [2]
[Sch05] Nicole Schweikardt. Arithmetic, first-order logic, and counting quantifiers. ACM Trans. Comput. Log., 6(3):634–671, 2005. doi:10.1145/1071596.1071602.
[SG26] Pierre Senellart, Anton Gnatenko. Descriptive Complexity in Lean: Completeness by First-Order Reductions. Sep 2026. arXiv:2609.18261, URL: https://arxiv.org/abs/2609.18261. [1]
[Sip83] Michael Sipser. Borel Sets and Circuit Complexity. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, 61–69. ACM, 1983. doi:10.1145/800061.808733. [1] [2]
[Sto76] Larry J. Stockmeyer. The Polynomial-Time Hierarchy. Theor. Comput. Sci., 3(1):1–22, 1976. doi:10.1016/0304-3975(76)90061-X. [1] [2] [3] [4] [5] [6] [7]
[SM73] Larry J. Stockmeyer, Albert R. Meyer. Word Problems Requiring Exponential Time: Preliminary Report. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC), 1–9. 1973. doi:10.1145/800125.804029. [1] [2] [3] [4]
[Sze88] Róbert Szelepcsényi. The Method of Forced Enumeration for Nondeterministic Automata. Acta Informatica, 26(3):279–284, 1988. doi:10.1007/BF00299636. [1] [2] [3] [4]
[Tra50] Boris A. Trakhtenbrot. The impossibility of an algorithm for the decidability problem on finite classes. Proceedings of the USSR Academy of Sciences, 70(4):569–572, 1950. In Russian. [1]
[Tse68] G. S. Tseitin. On the complexity of derivation in propositional calculus. In A. O. Slisenko, editor, Studies in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics, pages 115–125. Steklov Mathematical Institute, 1968. [1] [2] [3] [4] [5] [6] [7] [8]
[Var82] Moshe Y. Vardi. The Complexity of Relational Query Languages (Extended Abstract). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, 137–146. ACM, 1982. doi:10.1145/800070.802186. [1] [2] [3] [4]
[Vei98] Helmut Veith. Succinct Representation, Leaf Languages, and Projection Reductions. Inf. Comput., 142(2):207–236, 1998. doi:10.1006/INCO.1997.2696. [1] [2] [3]
[Vol99] Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. ISBN 978-3-540-64310-4. doi:10.1007/978-3-662-03927-4. [1] [2] [3] [4] [5]
[Wra76] Celia Wrathall. Complete Sets and the Polynomial-Time Hierarchy. Theor. Comput. Sci., 3(1):23–33, 1976. doi:10.1016/0304-3975(76)90062-1. [1] [2] [3]