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 Abstract Freely available
Right arrow Full Text (PDF)
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

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



References

    [1]  Arratia A, Ortiz C. Expressive power and complexity of a logic with quantifiers hat count proportions of sets. J. of Logic and Computation (2006) 16(6):817–840.[CrossRef]

    [2]  Ebbinghaus HD, Flum J. Finite Model Theory. (1995) Springer-Verlag.

    [3]  Etessami K, Immerman N. Reachability and the power of local ordering. Theoretical Comp. Sci (1995) 148(2):261–279.[CrossRef]

    [4]  Grädel E. Capturing complexity classes by fragments of second order logic. Theoretical Comp. Sci (1992) 101:35–57.[CrossRef]

    [5]  Immerman N. Nondeterministic space is closed under complement. SIAM Journal on Computing (1988) 17:935–938.[CrossRef][Web of Science]

    [6]  Immerman N. Descriptive Complexity. (1998) Springer.

    [7]  Keisler HJ. Hyperfinite model theory. In:. In: Logic Colloquium.—Gandy RC, Hyland JME, eds. (1977) 76. North-Holland.

    [8]  Libkin L, Wong L. Lower bounds for invariant queries in logics with counting. Theoretical Comp. Sci (2002) 288:153–180.[CrossRef]

    [9]  Stewart I. Logical description of monotone NP problems. J. Logic and Computation (1994) 4(4):337–357.[CrossRef]

    [10]  Szelepcsényi R. The method of forced enumeration for nondeterministic automata. Acta Informatica (1988) 26:279–284.[CrossRef][Web of Science]


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



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
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?