Generalized Quantifiers and Logical Reducibilities

DOI10.1093/logcom/5.2.213zbMath0815.03021OpenAlexW2031411912WikidataQ58215761 ScholiaQ58215761MaRDI QIDQ4763536

Anuj Dawar

Publication date: 17 April 1995

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://repository.upenn.edu/cis_reports/348

zbMATH Keywords

finite model theorycomplexity classespolynomial time computabilityLindström quantifierslogical reducibilityrecursive index sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (16)

Finite Variable Logics in Descriptive Complexity Theory ⋮ Relativization of Gurevich’s Conjectures ⋮ How to define a linear order on finite models ⋮ Capturing MSO with One Quantifier ⋮ Logics capturing relativized complexity classes uniformly ⋮ On vectorizations of unary generalized quantifiers ⋮ The hierarchy theorem for generalized quantifiers ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Circle graphs and monadic second-order logic ⋮ A constant-space sequential model of computation for first-order logic ⋮ On Complete Problems, Relativizations and Logics for Complexity Classes ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ A constant-space sequential model of computation for first-order logic ⋮ Fixed-Point Definability and Polynomial Time ⋮ On fixed-point logic with counting ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws

This page was built for publication: Generalized Quantifiers and Logical Reducibilities