Search

In this paper we establish a link between fuzzy and preferential semantics for description logics and Self-Organising Maps, which have been proposed as possible candidates to explain the psychological mechanisms underlying category generalisation. In particular, we show that the input/output behavior of a Self-Organising Map after training can be described by a fuzzy description logic interpretation as well as by a preferential interpretation, based on a concept-wise multipreference semantics, which takes into account preferences with respect to different concepts and has been recently proposed for ranked and for weighted defeasible description logics. Properties of the network can be proven by model checking on the fuzzy or on the preferential interpretation. Starting from the fuzzy interpretation, we also provide a probabilistic account for this neural network model., Comment: 31 pages, 1 figure. arXiv admin note: text overlap with arXiv:2008.13278

In this paper, we propose self-organising maps as possible candidates to explain the psychological mechanisms underlying category generalisation. Self-organising maps are psychologically and biologically plausible neural network models that can learn after limited exposure to positive category examples, without any need of contrastive information. They reproduce human behaviour in category generalisation, in particular, the Numerosity and Variability effects, which are usually explained with Bayesian tools. Where category generalisation is concerned, self-organising maps deserve attention to bridge the gap between the computational level of analysis in Marr's hierarchy (where Bayesian models are often situated) and the algorithmic level of analysis in which plausible mechanisms are described.

Recency effects are well documented in the adult and infant literature: recognition and recall memory are better for recently occurring events. We explore recency effects in infant categorization, which does not merely involve memory for individual items, but the formation of abstract category representations. We present a computational model of infant categorization that simulates category learning in 10-month-olds. The model predicts that recency effects outweigh previously reported order effects for the same stimuli. According to the model, infant behaviour at test should depend mainly on the identity of the most recent training item. We evaluate these predictions in a series of experiments with 10-month-old infants. Our results show that infant behaviour confirms the model’s prediction. In particular, at test infants exhibited a preference for a category outlier over the category average only if the final training item had been close to the average, rather than distant from it. Our results are consistent with a view of categorization as a highly dynamic process where the end result of category learning is not the overall average of all stimuli encountered, but rather a fluid representation that moves depending on moment-to-moment novelty. We argue that this is a desirable property of a flexible cognitive system that adapts rapidly to different contexts.

In this paper we present an extension of a visual auditory neural network model previously proposed by Mayor and Plunkett (2010) in order to explain the emergence of the taxonomic response in early childhood. The original model consists of two self-organizing maps (respectively, visual and acoustic) connected with Hebbian connections. With respect to the original model, our proposal adds two major features. First, our model follows a dynamic training regime, learning categories and word-object associations that evolve through time. Second, the visual and acoustic maps are Growing self-organizing maps that grow during training, when they are no longer able to consistently represent categories. With these two new characterizing features, our model replicates the performance of the original Mayor and Plunkett (2010)’s model, acquires psychological plausibility in the training regime, and avoids the risk of catastrophic interference.

Issue title: Special Issue on the 30th Italian Conference on Computational Logic: CILC 2015Guest editors: Marco Maratea, Viviana Mascardi, Davide Ancona and Alberto Pettorossi; International audience; We explore the extension of the notion of rational closure to logics lacking the finite model property, considering the logic SHIQ. We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a KB can be computed in EXPTIME based on a polynomial encoding of the rational extension of SHIQ into entailment in SHIQ. We discuss the extension of rational closure to more expressive description logics.

International audience; In this work we describe preferential Description Logics of typicality, a nonmonotonic extension of standard Description Logics by means of a typicality operator T allowing to extend a knowledge base with inclusions of the form T(C) ⊑ D, whose intuitive meaning is that “normally/typically Cs are also Ds”. This extension is based on a minimal model semantics corresponding to a notion of rational closure, built upon preferential models. We recall the basic concepts underlying preferential Description Logics. We also present two extensions of the preferential semantics: on the one hand, we consider probabilistic extensions, based on a distributed semantics that is suitable for tackling the problem of commonsense concept combination, on the other hand, we consider other strengthening of the rational closure semantics and construction to avoid the so called “blocking of property inheritance problem”.

The paper describes a preferential approach for dealing with exceptions in KLM preferential logics, based on the rational closure. It is well known that rational closure does not allow an independent handling of inheritance of different defeasible properties of concepts. In this work, we consider an alternative closure construction, called Multi Preference closure (MP-closure), which has been first considered for reasoning with exceptions in DLs. We reconstruct the notion of MP-closure in the propositional case and show that it is a natural (weaker) variant of Lehmann's lexicographic closure, which appears to be too bold in some cases. The MP-closure defines a preferential consequence relation that, although weaker than lexicographic closure, is stronger than Relevant Closure.

Starting from the observation that rational closure has the undesirable property of being an “all or nothing” mechanism, we here consider a multipreferential semantics, which enriches the preferential semantics underlying rational closure in order to separately deal with the inheritance of different properties in an ontology with exceptions. We show that the MP-closure of an \(\mathcal {ALC}\) knowledge base is a construction which is sound with respect to minimal entailment in the multipreference semantics for \(\mathcal {ALC}\).

International audience; In this paper we propose a non-monotonic extension of the Description Logic ALC for reasoning about prototypical properties and inheritance with exceptions. The resulting logic, called ALC + T-min, is built upon a previously introduced (monotonic) logic ALC + T that is obtained by adding a typicality operator T to ALC. The operator T is intended to select the "most normal" or "most typical" instances of a concept, so that knowledge bases may contain subsumption relations of the form T(C) subset of D ("T(C) is subsumed by D"), expressing that typical C-members are instances of concept D. From a knowledge representation point of view, the monotonic logic ALC + T is too weak to perform inheritance reasoning. In ALC + T-min, in order to perform non-monotonic inferences, we define a "minimal model" semantics over ALC + T. The intuition is that preferred or minimal models are those that maximize typical instances of concepts. By means of ALC + T-min we are able to infer defeasible properties of (explicit or implicit) individuals. We also present a tableau calculus for deciding ALC + T-min entailment that allows to give a complexity upper bound for the logic, namely that query entailment is in co-NExp(NP)

We present tableau calculi for some logics of nonmonotonic reasoning, as defined by Kraus, Lehmann and Magidor. We give a tableau proof procedure for all KLM logics, namely preferential, loop-cumulative, cumulative and rational logics. Our calculi are obtained by introducing suitable modalities to interpret conditional assertions. We provide a decision procedure for the logics considered, and we study their complexity., Comment: 54 pages + appendix with proofs

We propose a logical analysis of the concept of typicality, central in human cognition Rosch 1978. We start from a previously proposed extension of the basic Description Logic $$\mathcal {ALC}$$ with a typicality operator $$\mathbf{T}$$ that allows to consistently represent the attribution to classes of individuals of properties with exceptions as in the classic example i typical birds fly, ii penguins are birds but iii typical penguins don't fly. We then strengthen this extension in order to separately reason about the typicality with respect to different aspects e.g., flying, having nice feather: in the previous example, penguins may not inherit the property of flying, for which they are exceptional, but can nonetheless inherit other properties, such as having nice feather.

In this paper we provide a semantic reconstruction of rational closure. We first consider rational closure as defined by Lehman and Magidor [33] for propositional logic, and we provide a semantic characterization based on a minimal models mechanism on rational models. Then we extend the whole formalism and semantics to Description Logics, by focusing our attention to the standard ALC : we first naturally adapt to Description Logics Lehman and Magidor's propositional rational closure, starting from an extension of ALC with a typicality operator T that selects the most typical instances of a concept C (hence T ( C ) stands for typical C). Then, for the Description Logics, we define a minimal model semantics for the logic ALC and we show that it provides a semantic characterization for the rational closure of a Knowledge base. We consider both the rational closure of the TBox and the rational closure of the ABox.

We describe DysToPic, a theorem prover for the preferential Description Logic \(\mathcal {ALC}+\mathbf{T}_{min}\).This is a nonmonotonic extension of standard \(\mathcal {ALC}\) based on a typicality operator \(\mathbf{T}\), which enjoys a preferential semantics. DysToPic is a multi-engine Prolog implementation of a labelled, two-phase tableaux calculus for \(\mathcal {ALC}+\mathbf{T}_{min}\) whose basic idea is that of performing these two phases by different machines. The performances of DysToPic are promising, and significantly better than the ones of its predecessor PreDeLo 1.0 recently introduced.

We describe DysToPic, a theorem prover for the preferential Description Logic \(\mathcal {ALC}+\mathbf{T}_{min}\).This is a nonmonotonic extension of standard \(\mathcal {ALC}\) based on a typicality operator \(\mathbf{T}\), which enjoys a preferential semantics. DysToPic is a multi-engine Prolog implementation of a labelled, two-phase tableaux calculus for \(\mathcal {ALC}+\mathbf{T}_{min}\) whose basic idea is that of performing these two phases by different machines. The performances of DysToPic are promising, and significantly better than the ones of its predecessor PreDeLo 1.0 recently introduced.

In this paper we define an extension of the description logic \(\mathcal {SROIQ}\) based on a preferential semantics to introduce a notion of typicality in the language which allows defeasible inclusions to be represented in a knowledge base. We define a polynomial encoding of the resulting language into \(\mathcal {SROIQ}\), thus showing that reasoning in the preferential extension of \(\mathcal {SROIQ}\) has the same complexity as reasoning in \(\mathcal {SROIQ}\).

In this paper we propose a conditional logic called IBC to represent iterated belief revision systems. We propose a set of postulates for iterated revision which are a small variant of Darwiche and Pearl's ones. The conditional logic IBC has a standard semantics in terms of selection function models and provides a natural representation of epistemic states. We establish a correspondence between iterated belief revision systems and IBC-models. Our representation theorem does not entail Gardenfors' Triviality Result.

We describe PreDeLo 1.0 , a theorem prover for preferential Description Logics (DLs). These are nonmonotonic extensions of standard DLs based on a typicality operatorT, which enjoys a preferential semantics. PreDeLo 1.0 is a Prolog implementation of labelled tableaux calculi for such extensions, and it is able to deal with the preferential extension of the basic DL $\mathcal{ALC}$ as well as with the preferential extension of the lightweight DL DL '—' Lite core . The Prolog implementation is inspired by the "lean" methodology, whose basic idea is that each axiom or rule of the tableaux calculi is implemented by a Prolog clause of the program. Concerning $\mathcal{ALC}$ , PreDeLo 1.0 considers two extensions based, respectively, on Kraus, Lehmann and Magidor's preferential and rational entailment. In this paper, we also introduce a tableaux calculus for checking entailment in the rational extension of $\mathcal{ALC}$ .

This paper provides a general semantic framework for nonmonotonic reasoning, based on a minimal models semantics on the top of KLM systems for nonmonotonic reasoning. This general framework can be instantiated in order to provide a semantic reconstruction within modal logic of the notion of rational closure, introduced by Lehmann and Magidor. We give two characterizations of rational closure: the first one in terms of minimal models where propositional interpretations associated to worlds are fixed along minimization, the second one where they are allowed to vary. In both cases a knowledge base must be expanded with a suitable set of consistency assumptions, represented by negated conditionals. The correspondence between rational closure and minimal model semantics suggests the possibility of defining variants of rational closure by changing either the underlying modal logic or the comparison relation on models.

In this paper we introduce a tableau calculus for a nonmonotonic extension of the low complexity Description Logic DL-Litecore of the DL-Litecore family. The extension, called DL-LitecTmin, can be used to reason about typicality and defeasible properties. The calculus performs a two-phase computation to check whether a query is minimally entailed from the initial knowledge base. It is sound, complete and terminating. Furthermore, it is a decision procedure for DL-LitecTmin knowledge bases, whose complexity matches the known results for the logic, namely that entailment is in Π2p.

We introduce a tableau calculus for a nonmonotonic extension of low complexity Description Logic \(\mathcal{EL}^\bot\) that can be used to reason about typicality and defeasible properties. The calculus deals with Left Local knowledge bases in the logic \(\mathcal{EL}^{\bot} {\bf T}_{min}\) recently introduced in [8] . The calculus performs a two-phase computation to check whether a query is minimally entailed from the initial knowledge base. It is sound, complete and terminating. Furthermore, it is a decision procedure for Left Local \(\mathcal{EL}^{\bot} {\bf T}_{min}\) knowledge bases, whose complexity matches the known results for the logic, namely that entailment is in Π p 2.

In this paper we study the applicability of constructive conditional logics as a general framework to define decision procedures in access control logics. To this purpose, we formalize the assertion A says φ, whose intended meaning is that principal A says that φ, as a conditional implication. We introduce CondACL, which is a conservative extension of the logic ICL recently introduced by Garg and Abadi. We identify the conditional axioms needed to capture the basic properties of the "says" operator and to provide a proper definition of boolean principals. We provide a Kripke model semantics for the logic and we prove that the axiomatization is sound and complete with respect to the semantics. Moreover, we define a sound, complete, cut-free and terminating sequent calculus for CondACL, which allows us to prove that the logic is decidable. We argue for the generality of our approach by presenting canonical properties of some further well known access control axioms. The identification of canonical properties provides the possibility to craft access control logics that adopt any combination of axioms for which canonical properties exist.

Webrieflyoutlineourresearchactivity,startedinthe90s,inthefieldofnon-classicallogics.Inparticular,wedescribeour activity on the use of non-classical logics for knowledge representation and on proof methods for non-monotonic and conditional logics.

In this paper, we propose the logic Pmin, which is a nonmonotonic extension of Preferential logic P defined by Kraus, Lehmann and Magidor (KLM). In order to perform nonmonotonic inferences, we define a "minimal model" semantics. Given a modal interpretation of a minimal A-world as A ∧ □¬A, the intuition is that preferred, or minimal models are those that minimize the number of worlds where ¬□¬A holds, that is of A-worlds which are not minimal. We also present a tableau calculus for deciding entailment in Pmin.

In this paper we address the problem of verifying business process compliance with norms. To this end, we employ reasoning about actions in a temporal action theory. The action theory is defined through a combination of Answer Set Programming and Dynamic Linear Time Temporal Logic (DLTL). The temporal action theory allows us to formalize a business process as a temporal domain description, possibly including temporal constraints. Obligations in norms are captured by the notion of commitment, which is borrowed from the social approach to agent communication. Norms are represented using (possibly) non monotonic causal laws which (possibly) enforce new obligations. In this context, verifying compliance amounts to verify that no execution of the business process leaves some commitment unfulfilled. Compliance verification can be performed by Bounded Model Checking.

The paper introduces a framework based on constructive conditional logics to define axiomatization, semantics and proof methods for access control logics. We formalize the well known says operator as a conditional normal modality and, by considering some specific combinations of access control axioms, we define four access control logics, namely, CondUC ACL , Cond U4 ACL , CondIC ACL and Cond I4 ACL . Such logics integrate access control logics with intuitionistic conditional logics and provide a natural formulation of boolean principals. The well known “speaks for” operator introduced in the logic ABLP is defined on the top of the says modality. We provide a Kripke model semantics for the logics and we prove that their axiomatization is sound and complete with respect to the semantics. Also, we develop sound, complete, cut-free sequent calculi for them. For the logic CondUC ACL , which (as concerns atomic principals) is slightly stronger than the logic ICL recently introduced by Garg and Abadi, we also provide a terminating sequent calculus, thus proving that the logic is decidable and that validity in CondUC ACL is in PSPACE.

We present a tableau calculus for some fundamental systems of propositional conditional logics. We consider the conditional logics that can be characterized by preferential semantics (i.e., possible world structures equipped with a family of preference relations). For these logics, we provide a uniform completeness proof of the axiomatization with respect to the semantics, and a uniform labeled tableau procedure.

We present an extension of the low complexity Description Logic $\mathcal{EL}^{+^\bot}$ for reasoning about prototypical properties and inheritance with exceptions. We add to $\mathcal{EL}^{+^\bot}$ a typicality operator T, which is intended to select the "most normal" instances of a concept. In the resulting logic, called $\mathcal{EL}^{+^\bot}{\bf T}$, the knowledge base may contain subsumption relations of the form "T(C ) is subsumed by P ", expressing that typical C -members have the property P . We show that the problem of entailment in $\mathcal{EL}^{+^\bot}{\bf T}$ is in co-NP by proving a small model result.

We present an extension $\mathcal{EL}^{+^\bot}{\bf {\rm T}}$ of the description logic $\mathcal{EL}^{+^\bot}$ for reasoning about prototypical properties and inheritance with exceptions. $\mathcal{EL}^{+^\bot}{\bf {\rm T}}$ is obtained by adding to $\mathcal{EL}^{+^\bot}$ a typicality operator T, which is intended to select the "typical" instances of a concept. In $\mathcal{EL}^{+^\bot}{\bf {\rm T}}$ knowledge bases may contain inclusions of the form "T(C ) is subsumed by P ", expressing that typical C -members have the property P . We show that the problem of entailment in $\mathcal{EL}^{+^\bot}{\bf {\rm T}}$ is in co-NP .

A substantial body of experimental evidence has demonstrated that labels have an impact on infant categorization processes. Yet little is known regarding the nature of the mechanisms by which this effect is achieved. We distinguish between two competing accounts: supervised name-based categorization and unsupervised feature-based categorization. We describe a neurocomputational model of infant visual categorization, based on self-organizing maps, that implements the unsupervised feature-based approach. The model successfully reproduces experiments demonstrating the impact of labeling on infant visual categorization reported in Plunkett, Hu, and Cohen (2008). It mimics infant behavior in both the familiarization and testing phases of the procedure, using a training regime that involves only single presentations of each stimulus and using just 24 participant networks per experiment. The model predicts that the observed behavior in infants is due to a transient form of learning that might lead to the emergence of hierarchically organized categorical structure and that the impact of labels on categorization is influenced by the perceived similarity and the sequence in which the objects are presented. The results suggest that early in development, say before 12 months old, labels need not act as invitations to form categories nor highlight the commonalities between objects, but they may play a more mundane but nevertheless powerful role as additional features that are processed in the same fashion as other features that characterize objects and object categories.

In this paper we propose a nonmonotonic extension of the Description Logic $\mathcal{ALC}$ for reasoning about prototypical properties and inheritance with exception. The logic is built upon a previously introduced (monotonic) logic , that is obtained by adding a typicality operator T to $\mathcal{ALC}$. The operator T is intended to select the "most normal" or "most typical" instances of a concept, so that knowledge bases may contain subsumption relations of the form" T (C) is subsumed by P", expressing that typical C-members have the property P. In order to perform nonmonotonic inferences, we define a "minimal model" semantics for . The intuition is that preferred, or minimal models are those that maximise typical instances of concepts. By means of we are able to infer defeasible properties of (explicit or implicit) individuals. We also present a tableau calculus for deciding entailment.

We extend the Description Logic ALC with a "typicality" operator T that allows us to reason about the prototypical properties and inheritance with exceptions. The resulting logic is called ALC + T. The typicality operator is intended to select the "most normal" or "most typical" instances of a concept. In our framework, knowledge bases may then contain, in addition to ordinary ABoxes and TBoxes, subsumption relations of the form "T(C) is subsumed by P", expressing that typical C-members have the property P. The semantics of a typicality operator is defined by a set of postulates that are strongly related to Kraus-Lehmann-Magidor axioms of preferential logic P. We first show that T enjoys a simple semantics provided by ordinary structures equipped by a preference relation. This allows us to obtain a modal interpretation of the typicality operator. Using such a modal interpretation, we present a tableau calculus for deciding satisfiability of ALC + T knowledge bases. Our calculus gives a nondeterministic-exponential time decision procedure for satisfiability of ALC + T. We then extend ALC + T knowledge bases by a nonmonotonic completion that allows inferring defeasible properties of specific concept instances.

In this paper we present a tableau calculus for the rational logic R of default reasoning, introduced by Kraus, Lehmann and Magidor. Our calculus is obtained by introducing suitable modalities to interpret conditional assertions, and makes use of labels to represent possible worlds. We also provide a decision procedure for R and study its complexity.

We reformulate AGM postulates for belief revision systems that may contain conditional formulas. We show that we can establish a mapping between belief revision systems and conditionals by means of the so called Ramsey Test, without incurring Gärdenfors triviality result. We then derive the conditional logic BCR from our revision postulates by means of a strong version of the Ramsey Test. We give a sound and complete axiomatization of this logic with respect to its standard selection-function models semantics, and we prove its decidability. We finally show that there is an isomorphism between belief revision systems and selection function models of BCR via a representation theorem. The logic BCR provides a logical formalization of belief revision in the language of conditional logic.

We present tableau calculi for some logics of default reasoning, as defined by Kraus, Lehmann and Magidor. We give a tableau proof procedure for preferential and cumulative logics. Our calculi are obtained by introducing suitable modalities to interpret conditional assertions. Moreover, they give a decision procedure for the respective logics and can be used to establish their complexity.

We offer a solution to the triviality result by Gardenfors. His result claims that there are no non-trivial belief revision systems which satisfy the AGM postulates and are compatible with the Ramsey Test. We show that this result does no longer apply if we restrict some of the AGM postulates to deal only with the non-conditional part of epistemic states.

In this paper we introduce a conditional logic BC to represent belief revision. Logic BC has a standard semantics in terms of possible worlds structures with a selection function and has strong similarities with Stalnaker's logic C2. Moreover, Gardenfors' Triviality Result does not apply to BC. We provide a representation result, which shows that each belief revision system corresponds to a BC-model and every BC model satisfying the covering condition determines a belief revision system.

Reasoning about exceptions in ontologies is nowadays one of the challenges the description logics community is facing. The paper describes a preferential approach for dealing with exceptions in Description Logics, based on the rational closure. The rational closure has the merit of providing a simple and efficient approach for reasoning with exceptions, but it does not allow independent handling of the inheritance of different defeasible properties of concepts. In this work we outline a possible solution to this problem by introducing a weaker variant of the lexicographical closure, that we call skeptical closure, which requires to construct a single base. We develop a bi-preference semantics for defining a characterization of the skeptical closure.

We present KLMLean 2.0, a theorem prover for propositional KLM logics of nonmonotonic reasoning. KLMLean 2.0 implements some analytic tableaux calculi for these logics recently introduced. KLMLean 2.0 is inspired by the "lean" methodology, it is implemented in SICStus Prolog and it also contains a graphical interface written in Java.

We present FreeP 1.0 , a theorem prover for the KLM preferential logic P of nonmonotonic reasoning. FreeP 1.0 is a SICStus Prolog implementation of a free-variables, labelled tableau calculus for P , obtained by introducing suitable modalities to interpret conditional assertions. The performances of FreeP 1.0 are promising. FreeP 1.0 can be downloaded at http://www.di.unito.it/~pozzato/FreeP1.0 .

We report on a proof-checked version of Stone’s result on the representability of Boolean algebras via the clopen sets of a totally disconnected compact Hausdorff space. Our experiment is based on a proof verifier based on set theory, whose usability can in its turn benefit from fully formalized proofs of representation theorems akin to the one discussed in this note.

A (hereditarily finite) set/hyperset S can be completely depicted by a (finite pointed) graph GS—dubbed its membership graph— in which every node represents an element of the transitive closure of {S} and every arc represents a membership relation holding between its source and its target. In a membership graph different nodes must have different sets of successors and, more generally, if the graph is cyclic no bisimilar nodes are admitted. We call such graphs hyper-extensional. Therefore, the elimination of even a single node in a membership graph can cause different nodes to “collapse” (becoming representatives of the same set/hyperset) and the graph to loose hyper-extensionality and its original membership character. In this note we discuss the following problem: given S is it always possible to find a node s in GS whose deletion does not cause any collapse?