Skip Navigation


Logic Journal of IGPL Advance Access originally published online on January 1, 2009
Logic Journal of IGPL 2009 17(1):131-154; doi:10.1093/jigpal/jzn031
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
17/1/131    most recent
jzn031v1
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Arratia, A.
Right arrow Articles by Ortiz, C. E.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Approximate formulae for a logic that capture classes of computational complexity

Argimiro Arratia *

Dpto. de Matemática Aplicada Facultad de Ciencias Universidad de Valladolid Valladolid 47005, Spain E-mail: arratia{at}mac.uva.es

Carlos E. Ortiz {dagger}

Department of Mathematics and Computer Science Arcadia University 450 S. Easton Road, Glenside, PA 19038-3295, U.S.A. E-mail: ortiz{at}arcadia.edu


  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.

Key Words: Proportional quantifiers • approximate formulae • almost order • expressiveness • computational complexity • P • NL

Received for publication 21 May 2007.

Subject Classification: Logic in computer science, Descriptive Complexity

*Supported by grants Ramón y Cajal (MEC+FEDER-FSE); MOISES (TIN2005-08832-C03-02) and SINGACOM (MTM2004-00958), MEC–Spain

{dagger}Supported by a Faculty Award Grant from the Christian R. & Mary F. Lindback Foundation, and a Visiting Research Fellowship from University of Valladolid, Spain


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.