To access the full text documents, please follow this link:

Approximate formulae for a logic that capture classes of computational complexity
Arratia Quesada, Argimiro Alejandro; Ortiz, Carlos E.
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
This is a pre-copy-editing, author-produced PDF of an article accepted for publication in Logic Journal of IGPL following peer review. The definitive publisher-authenticated version Arratia, Argimiro; Ortiz, Carlos E. Approximate formulae for a logic that capture classes of computational complexity. Logic Journal of IGPL, 2009, vol. 17, p. 131-154 is available online at:
This paper presents a syntax of approximate formulae suited for the logic with counting quantifiers SOLP. This logic was formalised by us in [1] where, among other properties, we showed the following facts: (i) In the presence of a built–in (linear) order, SOLP can describe NP–complete problems and some of its fragments capture the classes P and NL; (ii) weakening the ordering relation to an almost order we can separate meaningful fragments, using a combinatorial tool adapted to these languages. The purpose of our approximate formulae is to provide a syntactic approximation to the logic SOLP, enhanced with a built-in order, that should be complementary of the semantic approximation based on almost orders, by means of producing logics where problems are syntactically described within a small counting error. We introduce a concept of strong expressibility based on approximate formulae, and show that for many fragments of SOLP with built-in order, including ones that capture P and NL, expressibility and strong expressibility are equivalent. We state and prove a Bridge Theorem that links expressibility in fragments of SOLP over almost-ordered structures to strong expressibility with respect to approximate formulae for the corresponding fragments over ordered structures. A consequence of these results is that proving inexpressibility over fragments of SOLP with built-in order could be done by proving inexpressibility over the corresponding fragments with built-in almost order, where separation proofs are allegedly easier.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica::Aplicacions informàtiques a la física i l‘enginyeria
Computer logic
Computational complexity
Complexitat computacional
Lògica informàtica
Oxford University Press

Show full item record

Related documents

Other documents of the same author

Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.