99 (1) 2010


  1. Grill Determined L-Approach Merotopological Spaces
    Mona Khare,  Surabhi Tiwari 1-12
    The present paper is devoted to the study of grill determined L-approach merotopological spaces. The category having such spaces as objects is shown to be a topological construct (its initial and final structures are provided explicitly). The lattice structure of the family of all these spaces is also discussed. In the classical theory, this category (that is, when L={0,1}) is a supercategory of the category of pseudo metric spaces and nonexpansive maps.
  2. Evolutionary Rough Parallel Multi-Objective Optimization Algorithm
    Ujjwal Maulik,  Anasua Sarkar 13-27
    A hybrid unsupervised learning algorithm, which is termed as Parallel Rough-based Archived Multi-Objective Simulated Annealing (PARAMOSA), is proposed in this article. It comprises a judicious integration of the principles of the rough sets theory and the scalable distributed paradigm with the archived multi-objective simulated annealing approach. While the concept of boundary approximations of rough sets in this implementation, deals with the incompleteness in the dynamic classification method with the quality of classification coefficient as the classificatory competence measurement, the time-efficient parallel approach enables faster convergence of the Pareto-archived evolution strategy. It incorporates both the rough set-based dynamic archive classification method and the distributed implementation as a two-phase speedup strategy in this algorithm. A measure of the amount of domination between two solutions has been incorporated in this work to determine the acceptance probability of a new solution with an improvement in the spread of the non-dominated solutions in the Pareto-front by adopting rough sets theory. A complexity analysis of the proposed algorithm is provided. An extensive comparative study of the proposed algorithm with three other existing and well-known Multi-Objective Evolutionary Algorithms (MOEAs) demonstrate the effectiveness of the former with respect to four existing performance metrics and eleven benchmark test problems of varying degrees of difficulties. The superiority of this new parallel implementation over other algorithms also has been demonstrated in timing, which achieves a near optimal speedup with a minimal communication overhead.
  3. Matrix Graph Grammars with Application Conditions
    Pedro Pablo Pérez Velasco,  Juan de Lara 29-62
    In the Matrix approach to graph transformation we represent simple digraphs and rules with Boolean matrices and vectors, and the rewriting is expressed using Boolean operators only. In previous works, we developed analysis techniques enabling the study of the applicability of rule sequences, their independence, state reachability and the minimal graph able to fire a sequence.
    In the present paper we improve our framework in two ways. First, we make explicit (in the form of a Boolean matrix) some negative implicit information in rules. This matrix (called nihilation matrix) contains the elements that, if present, forbid the application of the rule (i.e. potential dangling edges, or newly added edges, which cannot be already present in the simple digraph). Second, we introduce a novel notion of application condition, which combines graph diagrams together with monadic second order logic. This allows for more flexibility and expressivity than previous approaches, as well as more concise conditions in certain cases. We demonstrate that these application conditions can be embedded into rules (i.e. in the left hand side and the nihilation matrix), and show that the applicability of a rule with arbitrary application conditions is equivalent to the applicability of a sequence of plain rules without application conditions. Therefore, the analysis of the former is equivalent to the analysis of the latter, showing that in our framework no additional results are needed for the study of application conditions. Moreover, all analysis techniques of [21, 22] for the study of sequences can be applied to application conditions.
  4. A Generic Approach to Connector Architectures Part I: The General Framework
    Fernando Orejas,  Hartmut Ehrig,  Markus Klein,  Julia Padberg,  Elvira Pino,
    Sonia Pérez 63-93
    The aim of this paper is to present a generic framework for the modelling of component-based systems using architectural connectors. More precisely, concepts of component, connector and architecture are presented in a formal generic way, which are independent of any semi-formal or formal modelling approach. The idea is that one could use this framework to define component and connector notions for every given modelling formalism. As a main result, we define the semantics of architectures using graph transformation, showing that the semantics is independent of the order in which the connections are computed, and that the semantics is compatible with transformation. In the continuation of this paper, we show the applicability of our ideas. In particular, our framework is instantiated by Petri nets and CSP, including a case study using Petri Nets.
  5. A Generic Approach to Connector Architectures Part II: Instantiation to Petri Nets and CSP
    Fernando Orejas,  Hartmut Ehrig,  Markus Klein,  Julia Padberg,  Elvira Pino,
    Sonia Pérez 95-124
    The aim of this paper is to show how the generic approach to connector architectures, presented in the first part of this work, can be applied to a given modeling formalism to define architectural component and connector notions associated to that formalism. Starting with a review of the generic approach, in this second part of the paper we consider two modeling formalisms: elementary Petri nets and CSP. As main results we show that both cases satisfy the axioms of our component framework, so that the results concerning the semantics of architectures can be applied. Moreover, a small case study in terms of Petri Nets is presented in order to show how the results can be applied to a connector architecture based on Petri nets.

99 (2) 2010


  1. Methodologies for Intelligent Systems. Preface i-ii
  2. Solving Sequential Planning Problems via Constraint Satisfaction
    Roman Barták,  Daniel Toropila 125-145
    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 constraint models 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.
  3. A Framework for Iterated Belief Revision Using Possibilistic Counterparts to Jeffrey's Rule
    Salem Benferhat,  Didier Dubois,  Henri Prade,  Mary-Anne Williams 147-168
    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.
  4. Interval-Valued Fuzzy Galois Connections: Algebraic Requirements and Concept Lattice Construction
    Yassine Djouadi,  Henri Prade 169-186
    Fuzzy formal concept analysis is concerned with 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.
  5. Fuzzy Clustering for Semantic Knowledge Bases
    Floriana Esposito, Claudia d'Amato,  Nicola Fanizzi 187-205
    This work focusses on the problem of clustering resources contained in knowledge bases represented through multi-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.
  6. Autonomy-Oriented Search in Dynamic Community Networks: A Case Study in Decentralized Network Immunization
    Jiming Liu, Chao Gao,  Ning Zhong 207-226
    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.
  7. Identifying Prime Implicate Branches in Reduced Implicate Tries
    Neil V. Murray, Erik Rosenthal 227-243
    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.

99 (3) 2010


  1. Arrow Index of a Fuzzy Choice Function
    Irina Georgescu 245-261
    The Arrow index of a fuzzy choice function C is a measure of the degree to which C satisfies the Fuzzy Arrow Axiom, a fuzzy version of the classical Arrow Axiom. The main result of this paper shows that A(C) characterizes the degree to which C is full rational. We also obtain a method for computing A(C). The Arrow index allows to rank the fuzzy choice functions with respect to their rationality. Thus, if for solving a decision problem several fuzzy choice functions are proposed, by the Arrow index the most rational one will be chosen.
  2. Computing Supports of Conjunctive Queries on Relational Tables with Functional Dependencies
    Tao-Yuan Jen,  Dominique Laurent, Nicolas Spyratos 263-292
    The problem of mining all frequent queries on a relational table is a problem known to be intractable even for conjunctive queries. In this article, we restrict our attention to conjunctive projection-selection queries and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions, we define and characterize two pre-orderings with respect to which the support measure is shown to be anti-monotonic. Each of these pre-orderings induces an equivalence relation for which all queries of the same equivalence class have the same support.
    The goal of this article is not to provide algorithms for the computation of frequent queries, but rather to provide basic properties of pre-orderings and their associated equivalence relations showing that functional dependencies can be used for an optimized computation of supports of conjunctive queries. In particular, we show that one of the two pre-orderings characterizes anti-monotonicity of the support, while the other one refines the former, but allows to characterize anti-monotonicity with respect to a given table, only. Basic computational implications of these properties are discussed in the article.
  3. Relational Contexts and Relational Concepts
    Feng Jiang,  Yuefei Sui and Cungen Cao 293-314
    Formal concept analysis (FCA) is a mathematical description and theory of concepts implied in formal contexts. And the current formal contexts of FCA aim to model the binary relations between individuals (objects) and attributes in the real world. In the real world we usually describe each individual by some attributes, which induces the relations between individuals and attributes. But there also exist many relations between individuals, for instance, the parent-children relation in a family. In this paper, to model the relations between individuals in the real world, we propose a new context - relational context for FCA, which contains a set U of objects and a binary relation r on U. Corresponding to the formal concepts in formal contexts, we present different kinds of relational concepts in relational contexts, which are the pairs of sets of objects. First we define the standard relational concepts in relational contexts. Moreover, we discuss the indirect relational concepts and negative relational concepts in relational contexts, which aim to concern the indirection and negativity of the relations in relational contexts, respectively. Finally, we define the hybrid relational concepts in relational contexts, which are the combinations of any two different kinds of relational concepts. In addition, we also discuss the application of relational contexts and relational concepts in the supply chain management field.
  4. Separating Multi-Color Points on a Plane with Fewest Axis-Parallel Lines
    Subhashis Majumder , Subhas C. Nandy,  Bhargab B. Bhattacharya 315-324
    In this paper, we deal with the problem of partitioning a set of coplanar points of more than one colors into monochromatic cells using minimum number of axis-parallel straight lines. It is first shown that the problem is NP-hard. A fast heuristic is then presented to solve this problem. Experimental results on randomly generated instances indicate that the proposed method is much faster than the existing techniques, with minor degradation in the cost of the partition.
  5. On the State Complexity of Scattered Substrings and Superstrings
    Alexander Okhotin 325-338
    It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least 2[n/2]−2 states (the known upper bound is 2n), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least 2√{2n+30}−6 states. A similar state complexity function for scattered superstrings is determined to be exactly 2n−2+1 for an alphabet of at least n−2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least [1/5] 4√{[n/2]} n−[3/4].
  6. Set-theoretical Constructions of Boolean Functions and theirs Applications
    in Logic Synthesis

    Bohdan Rytsar,  Piotr Romanowski,  Adrian Shvay 339-354
    In this paper a creation of new numerical set-theoretical constructions of Boolean functions with their properties has been presented. The parted conjuncterms and decomposition clones which can be used for realization of different optimization logic synthesis of digital devices and systems have been proposed. Set theoretical operations and procedures with these constructions have been considered. Examples which illustrate simplicity of their practical realization have been presented. Moreover, the paper includes the comparison of new results obtained on the basis of the proposed approach with the results obtained by means of commercial software Quartus II of Altera.


99 (4) 2010


  1. An Interface Group for Process Components
    Jan A. Bergstra,  Cornelis A. Middelburg 355-382
    We take a process component as a pair of an interface and a behaviour. We study the composition of interacting process components in the setting of process algebra. We formalize the interfaces of interacting process components by means of an interface group. An interesting feature of the interface group is that it allows for distinguishing between expectations and promises in interfaces of process components. This distinction comes into play in case components with both client and server behaviour are involved.
  2. Algebraic Ordinals
    Stephen L. Bloom,  Zoltan Ésik 383-407
    An algebraic tree T is one determined by a finite system of fixed point equations. The frontier Fr(T) of an algebraic tree T is linearly ordered by the lexicographic order < l. If (Fr(T) < l) is well-ordered, its order type is an algebraic ordinal. We prove that the algebraic ordinals are exactly the ordinals less than www .
  3. Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem
    Sebastian Deorowicz 409-433
    The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed.
  4. Solvability of the Halting and Reachability Problem for Binary 2-tag Systems
    Liesbeth De Mol 435-471
    In this paper a detailed proof will be given of the solvability of the halting and reachability problem for binary 2-tag systems.
  5. Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals
    Tomás Masopust 473-480
    Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.