Skip Navigation


Journal of Logic and Computation Advance Access originally published online on August 18, 2006
Journal of Logic and Computation 2006 16(6):817-840; doi:10.1093/logcom/exl011
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
16/6/817    most recent
exl011v1
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 Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (1)
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, 2006. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Articles

Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets

Argimiro Arratia

Dpto. de Matemática Aplicada Facultad de Ciencias, Universidad de Valladolid, Spain.

Carlos E. Ortiz

Department of Mathematics and Computer Science Arcadia University, USA. E-mail: ortiz{at}arcadia.edu

E-mail: arratia{at}mac.uva.es


  Abstract

We present a second-order logic of proportional quantifiers, Formula , which is essentially a first-order language extended with quantifiers that act upon second-order variables of a given arity r and count the fraction of elements in a subset of r-tuples of a model that satisfy a formula. Our logic is capable of expressing proportional versions of different problems of complexity up to NP-hard as, for example, the problem of deciding if at least a fraction 1/n of the set of vertices of a graph form a clique; and fragments within our logic capture complexity classes as NL and P, with auxiliary ordering relation. When restricted to monadic second-order variables, our logic of proportional quantifiers admits a semantic approximation based on almost linear orders, which is not as weak as other known logics with counting quantifiers (restricted to almost orders), for it does not have the bounded number of degrees property. Moreover, we show that, in this almost-ordered setting, different fragments of this logic vary in their expressive power, and show the existence of an infinite hierarchy inside our monadic language. We extend our inexpressibility result of almost-ordered structure to a fragment of Formula , which in the presence of full order captures P. To obtain all our inexpressibility results, we developed combinatorial games appropriate for these logics, whose application could go beyond the almost-ordered models and hence are interesting by themselves.

Keywords: Descriptive complexity; counting quantifiers; almost order; definability; P; NL


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.