Many researchers have suggested that the psychological complexity of a concept is related to the length of its representation in a language of thought. As yet, however, there are few concrete proposals about the nature of this language. This paper makes one such proposal: the language of thought allows first order quantification (quantificationover objects) more readily than second-order quantification (quantification over features). To support this proposal we present behavioral results froma concept learning study inspired by the work of Shepard, Hovland and Jenkins. Humans can learn and think about many kinds of concepts, including natural kinds such as elephant and water and nominal kinds such as grandmother and prime number.

Cropper, Andrew (Imperial College London) | Muggleton, Stephen H. (Imperial College London)

Most logic-based machine learning algorithms rely on an Occamist bias where textual complexity of hypotheses is minimised. Within Inductive Logic Programming (ILP), this approach fails to distinguish between the efficiencies of hypothesised programs, such as quick sort (O(n log n)) and bubble sort (O(n2)).

Cozman, Fabio Gagliardi, Mauá, Denis Deratani

We examine the meaning and the complexity of probabilistic logic programs that consist of a set of rules and a set of independent probabilistic facts (that is, programs based on Sato's distribution semantics). We focus on two semantics, respectively based on stable and on well-founded models. We show that the semantics based on stable models (referred to as the "credal semantics") produces sets of probability measures that dominate infinitely monotone Choquet capacities; we describe several useful consequences of this result. We then examine the complexity of inference with probabilistic logic programs. We distinguish between the complexity of inference when a probabilistic program and a query are given (the inferential complexity), and the complexity of inference when the probabilistic program is fixed and the query is given (the query complexity, akin to data complexity as used in database theory). We obtain results on the inferential and query complexity for acyclic, stratified, and normal propositional and relational programs; complexity reaches various levels of the counting hierarchy and even exponential levels.

Borgwardt, Stefan (Technische Universität Dresden) | Distel, Felix (Technische Universität Dresden) | Peñaloza, Rafael (Technische Universität Dresden)

In the last few years, there has been a large effort for analyzing the computational properties of reasoning in fuzzy description logics. This has led to a number of papers studying the complexity of these logics, depending on the chosen semantics. Surprisingly, despite being arguably the simplest form of fuzzy semantics, not much is known about the complexity of reasoning in fuzzy description logics w.r.t.

Bozzelli, Laura (Technical University of Madrid) | Ditmarsch, Hans van (LORIA, CNRS / University of Lorraine) | Pinchinat, Sophie (IRISA/INRIA, University of Rennes)

We investigate the complexity of satisfiability for one-agent refinement modal logic (RML), an extension of basic modal logic (ML) obtained by adding refinement quantifiers on structures. RML is known to have the same expressiveness as ML, but the translation of RML into ML is of non-elementary complexity, and RML is at least doubly exponentially more succinct than ML. In this paper we show that RML-satisfiability is only' singly exponentially harder than ML-satisfiability, the latter being a well-known PSPACE-complete problem.