Approximate formulae for a logic that capture classes of computational complexity

DOI10.1093/JIGPAL/JZN031MaRDI QIDQ3613175zbMATH OpenOpenAlexFDO

Authors Carlos E. P. Ortiz, Argimiro Arratia

Publication date 11 March 2009

Published in Logic Journal of the IGPL (Search for Journal in Brave)

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

zbMATH Keywords

almost orderapproximate formulaecomputational complexityexpressivenessNLPproportional quantifiers

Mathematics Subject Classification ID

Logic in computer science (03B70) 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)

Recommendations

• LATIN 2004: Theoretical Informatics
• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• Counting Proportions of Sets: Expressive Power with Almost Order
• Logics for complexity classes
• scientific article; zbMATH DE number 1841815

Cited in

(5)

• Applicative theories for logarithmic complexity classes
• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• Counting Proportions of Sets: Expressive Power with Almost Order
• LATIN 2004: Theoretical Informatics
• Logics capturing relativized complexity classes uniformly

This page was built for publication: Approximate formulae for a logic that capture classes of computational complexity

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