Counting Proportions of Sets: Expressive Power with Almost Order

DOI10.1007/11682462_14zbMATH Open1145.68431OpenAlexW1506160289MaRDI QIDQ3525752FDOQ3525752

Authors: Carlos E. P. Ortiz, Argimiro Arratia 

Publication date: 18 September 2008

Published in: LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11682462_14

Recommendations

• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• On the expressive power of counting
• A logical characterization of the counting hierarchy
• Approximate formulae for a logic that capture classes of computational complexity
• The expressive power of fixed-point logic with counting

zbMATH Keywords

computational complexityexpressivenessNLPproportional quantifiersalmost order

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Combinatorial games (91A46)

Cited In (2)

• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• Approximate formulae for a logic that capture classes of computational complexity

This page was built for publication: Counting Proportions of Sets: Expressive Power with Almost Order

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