Counting Proportions of Sets: Expressive Power with Almost Order

DOI10.1007/11682462_14MaRDI QIDQ3525752zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

almost ordercomputational complexityexpressivenessNLPproportional quantifiers

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)

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

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)