References

• [AHV95] Serge Abiteboul, Richard Hull, Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. ISBN 0-201-53771-0. [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]
• [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]
• [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, volume 171 of Lecture Notes in Computer Science, 357–365. Springer, 1983. doi:10.1007/3-540-13331-3_51. [1] [2] [3]
• [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]
• [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]
• [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 Grä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]
• [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]
• [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]
• [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] [5]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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] Róbert Szelepcsényi. The Method of Forced Enumeration for Nondeterministic Automata. Acta Informatica, 26(3):279–284, 1988. doi:10.1007/BF00299636. [1] [2] [3] [4] [5]
• [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]
• [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]