Skip Navigation


The Computer Journal Advance Access originally published online on July 30, 2007
The Computer Journal 2008 51(3):385-404; doi:10.1093/comjnl/bxm034
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
51/3/385    most recent
bxm034v2
bxm034v1
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 van Rooij, I.
Right arrow Articles by Wareham, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2007. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Parameterized Complexity in Cognitive Modeling: Foundations, Applications and Opportunities

Iris van Rooij1,* and Todd Wareham2

1 Nijmegen Institute for Cognition and Information, Radboud University Nijmegen, Nijmegen, The Netherlands
2 Department of Computer Science, Memorial University of Newfoundland, St. John's, NL, Canada

* Corresponding author: i.vanrooij{at}nici.ru.nl

Received 10 June 2006; revised 20 September 2006

In cognitive science, natural cognitive processes are generally conceptualized as computational processes: they serve to transform sensory and mental inputs into mental and action outputs. At the highest level of abstraction, computational models of cognitive processes aim at specifying the computational problem computed by the process under study. Because computational problems are realistic cognitive models only insofar as they can plausibly be computed by the human brain given its limited resources for computation, computational tractability provides a useful constraint on cognitive models. In this paper, we consider the particular benefits of the parameterized complexity framework for identifying sources of intractability in cognitive models. We review existing applications of the parameterized framework to this end in the domains of perception, action and higher cognition. We further identify important opportunities and challenges for future research. These include the development of new methods for complexity analyses specifically tailored to the reverse engineering perspective underlying cognitive science.

Key Words: cognitive modeling • parameterized complexity


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.