Approximate formulae for a logic that capture classes of computational complexity

DOI10.1093/JIGPAL/JZN031zbMATH Open1155.03014OpenAlexW2072189956MaRDI QIDQ3613175

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

computational complexityexpressivenessNLPapproximate formulaeproportional 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 (2)

Logics capturing relativized complexity classes uniformly ⋮ Applicative theories for logarithmic complexity classes

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