99 (1) 2010
- 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.
- 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.
- 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.
- 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.
- 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
- Methodologies for Intelligent Systems. Preface i-ii
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- 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 2^{n}),
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 2^{n−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]}.
- 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
- 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.
- 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 w^{ww }.
- 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.
- 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.
- 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.