Fundamenta Informaticae - Volume 99, issue 2

Article Type: Other

DOI: 10.3233/FI-2010-241

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. i-ii, 2010

Authors: Barták, Roman | Toropila, Daniel

Article Type: Research Article

Abstract: Planning problems deal with finding a sequence of actions that transfer the initial state of the world into a desired state. Frequently such problems are solved by dedicated algorithms but there exist planners based on translating the planning problem into a different formalism such as constraint satisfaction or Boolean satisfiability and using a general solver for this formalism. The paper describes how to enhance existing constraintmodels of sequential planning problems by using techniques such as symmetry …breaking (dominance rules), singleton consistency, nogoods, lifting, or techniques motivated by the partial-order planning. Show more

Keywords: planning, constraint models, symmetry breaking, lifting, redundant constraints, search strategy

DOI: 10.3233/FI-2010-242

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. 125-145, 2010

Authors: Benferhat, Salem | Dubois, Didier | Prade, Henri | AnneWilliams, Mary-Anne

Article Type: Research Article

Abstract: Intelligent agents require methods to revise their epistemic state as they acquire new information. Jeffrey's rule, which extends conditioning to probabilistic inputs, is appropriate for revising probabilistic epistemic states when new information comes in the form of a partition of events with new probabilities and has priority over prior beliefs. This paper analyses the expressive power of two possibilistic counterparts to Jeffrey's rule for modeling belief revision in intelligent agents. We show that this rule can …be used to recover several existing approaches proposed in knowledge base revision, such as adjustment, natural belief revision, drastic belief revision, and the revision of an epistemic state by another epistemic state. In addition, we also show that some recent forms of revision, called improvement operators, can also be recovered in our framework. Show more

Keywords: Belief revision, Jeffrey's rule, possibility theory

DOI: 10.3233/FI-2010-243

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. 147-168, 2010

Authors: Djouadi, Yassine | Prade, Henri

Article Type: Research Article

Abstract: Fuzzy formal concept analysis is concernedwith formal contexts expressing scalar-valued fuzzy relationships between objects and their properties. Existing fuzzy approaches assume that the relationship between a given object and a given property is a matter of degree in a scale L (generally [0,1]). However, the extent to which "object o has property a" may be sometimes hard to assess precisely. Then it is convenient to use a sub-interval from the scale L rather than a precise …value. Such formal contexts naturally lead to interval-valued fuzzy formal concepts. The aim of the paper is twofold. We provide a sound minimal set of algebraic requirements for interval-valued implications in order to fulfill the fuzzy closure properties of the resulting Galois connection. Secondly, a new approach based on a generalization of Gödel implication is proposed for building the complete lattice of all interval-valued fuzzy formal concepts. Show more

Keywords: Formal concept analysis, Interval-valued fuzzy formal contexts, Algebraic closure operators, Extended Gödel implication, Concepts lattice construction

DOI: 10.3233/FI-2010-244

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. 169-186, 2010

Authors: Esposito, Floriana | d'Amato, Claudia | Fanizzi, Nicola

Article Type: Research Article

Abstract: This work focusses on the problem of clustering resources contained in knowledge bases represented throughmulti-relational standard languages that are typical for the context of the Semantic Web, and ultimately founded in Description Logics. The proposed solution relies on effective and language-independent dissimilarity measures that are based on a finite number of dimensions corresponding to a committee of discriminating features, that stands for a context, represented by concept descriptions in Description Logics. The …proposed clustering algorithm expresses the possible clusterings in tuples of central elements: in this categorical setting, we resort to the notion of medoid, w.r.t. the given metric. These centers are iteratively adjusted following the rationale of fuzzy clustering approach, i.e. one where the membership to each cluster is not deterministic but graded, ranging in the unit interval. This better copes with the inherent uncertainty of the knowledge bases expressed in Description Logics which adopt an open-world semantics. An extensive experimentation with a number of ontologies proves the feasibility of our method and its effectiveness in terms of major clustering validity indices. Show more

Keywords: Clustering, Multi-relational learning, Description Logics, Ontology, Semantic Web Mining

DOI: 10.3233/FI-2010-245

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. 187-205, 2010

Authors: Liu, Jiming | Gao, Chao | Zhong, Ning

Article Type: Research Article

Abstract: In recent years, immunization strategies have been developed for stopping epidemics in complex-network-like environments. Yet it still remains a challenge for existing strategies to deal with dynamically-evolving networks that contain community structures, though they are ubiquitous in the real world. In this paper, we examine the performances of an autonomy-oriented distributed search strategy for tackling such networks. The strategy is based on the ideas of self-organization and positive feedback from Autonomy-Oriented Computing …(AOC). Our experimental results have shown that autonomous entities in this strategy can collectively find and immunize most highly-connected nodes in a dynamic, community-based network within a few steps. Show more

Keywords: Autonomy-oriented computing, complex networks, self-organization, immunization strategy, and distributed search

DOI: 10.3233/FI-2010-246

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. 207-226, 2010

Authors: Murray, Neil V. | Rosenthal, Erik

Article Type: Research Article

Abstract: The reduced implicate trie is a data structure that was introduced in [12] as a target language for knowledge compilation. It has the property that, even when large, it guarantees that a query can be processed in time linear in the size of the query, regardless of the size of the compiled knowledge base. In this paper, the branches of a reduced implicate trie that correspond to prime implicates are characterized. A technique is developed for …finding and marking nodes for which all descending branches correspond to non-prime implicates. This is extended to allow the discovery of prime implicate subsets of queries with a "yes" answer. Show more

Keywords: Reduced implicate tries, prime implicates, knowledge compilation

DOI: 10.3233/FI-2010-247

Citation: Fundamenta Informaticae, vol. 99, no. 2, pp. 227-243, 2010