The expressive power of finitely many generalized quantifiers

DOI10.1006/inco.1995.1166zbMath0849.68034OpenAlexW2149330764WikidataQ58215771 ScholiaQ58215771MaRDI QIDQ1908344

Lauri Hella, Anuj Dawar

Publication date: 4 November 1996

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1995.1166

zbMATH Keywords

first-order logicfixed point logic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Question answering and database querying: bridging the gap with generalized quantification, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Where First-Order and Monadic Second-Order Logic Coincide