dc.contributor |
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
dc.contributor.author |
Arratia Quesada, Argimiro Alejandro |
dc.contributor.author |
Ortiz, Carlos E. |
dc.date |
2009-02 |
dc.identifier.citation |
Arratia, A.; Ortiz, C. Approximate formulae for a logic that capture classes of computational complexity. "Logic Journal of IGPL", Febrer 2009, vol. 17, núm. 1, p. 131-154. |
dc.identifier.citation |
1367-0751 |
dc.identifier.citation |
10.1093/jigpal/jzn031 |
dc.identifier.uri |
http://hdl.handle.net/2117/8034 |
dc.language.iso |
eng |
dc.publisher |
Oxford University Press |
dc.relation |
http://jigpal.oxfordjournals.org/cgi/content/abstract/17/1/131 |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica::Aplicacions informàtiques a la física i l‘enginyeria |
dc.subject |
Computer logic |
dc.subject |
Computational complexity |
dc.subject |
Complexitat computacional |
dc.subject |
Lògica informàtica |
dc.title |
Approximate formulae for a logic that capture classes of computational complexity |
dc.type |
info:eu-repo/semantics/submittedVersion |
dc.type |
info:eu-repo/semantics/article |
dc.description.abstract |
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: http://jigpal.oxfordjournals.org/cgi/reprint/17/1/131?maxtoshow=&hits=10&RESULTFORMAT=&fulltext=Approximate+formulae+for+a+logic+that+capture+classes+of+computational+complexity&searchid=1&FIRSTINDEX=0&resourcetype=HWCIT |
dc.description.abstract |
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. |
dc.description.abstract |
Peer Reviewed |