The expressive power of finitely many generalized quantifiers

DOI10.1006/INCO.1995.1166MaRDI QIDQ1908344zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar, Lauri Hella

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)

Recommendations

• Relativized logspace and generalized quantifiers over finite ordered structures
• Rank hierarchies for generalized quantifiers
• Logical hierarchies in PTIME
• scientific article; zbMATH DE number 1104165
• The hierarchy theorem for generalized quantifiers

Cited in

(18)

• The hierarchy theorem for generalized quantifiers
• Question answering and database querying: bridging the gap with generalized quantification
• Generalized lower and upper approximations in quantales
• On vectorizations of unary generalized quantifiers
• Canonical Gentzen-Type Calculi with (n,k)-ary Quantifiers
• Generalized Quantifiers and Logical Reducibilities
• scientific article; zbMATH DE number 4039872 (Why is no real title available?)
• scientific article; zbMATH DE number 1615238 (Why is no real title available?)
• On the ordered conjecture
• On the expressibility hierarchy of Magidor-Malitz quantifiers
• On the generation of quantified lemmas
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Game comonads \& generalised quantifiers
• Where first-order and monadic second-order logic coincide
• scientific article; zbMATH DE number 4027448 (Why is no real title available?)
• scientific article; zbMATH DE number 1392296 (Why is no real title available?)
• scientific article; zbMATH DE number 1163932 (Why is no real title available?)
• First order logic, fixed point logic and linear order

This page was built for publication: The expressive power of finitely many generalized quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908344)