Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets

DOI10.1093/LOGCOM/EXL011zbMATH Open1118.03020OpenAlexW2149816638MaRDI QIDQ3431975

Carlos E. P. Ortiz, Argimiro Arratia

Publication date: 13 April 2007

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/9280

zbMATH Keywords

definabilitysecond-order logiccomplexity classesdescriptive complexitycounting quantifiersproportional quantifiersalmost order

Mathematics Subject Classification ID

Logic in computer science (03B70) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (3)

The Complexity of Counting Quantifiers on Equality Languages ⋮ Quantifiers in logic and proof-search using permissive-nominal terms and sets ⋮ Lower bounds for invariant queries in logics with counting.

This page was built for publication: Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets