97 (1-2) 2009


  1. Quantization Step Parity-based Steganography for MP3 Audio
    Yan Diqun,  Wang Rangding,  Zhang Liguang 1-14
    Petitcolas has proposed a steganographic technique called MP3Stego which can hide secret messages in a MP3 audio. This technique is well-known because of its high capacity. However, in rare cases, the normal audio encoding process will be terminated due to the endless loop problem caused by embedding operation. In addition, the statistical undetectability of MP3Stego can be further improved. Inspired by MP3Stego, a new steganographic method for MP3 audio is proposed in this paper. The parity bit of quantization step rather than the parity bit of block size in MP3Stego is employed to embed secret messages. Compared with MP3Stego, the proposed method can avoid the endless loop problem and achieve better imperceptibility and higher security.
  2. A Recursive Classifier System for Partially Observable Environments
    Ali Hamzeh,  Sattar Hashemi,  Ashkan Sami,  Adel Rahmani 15-40
    Previously we introduced Parallel Specialized XCS (PSXCS), a distributed-architecture classifier system that detects aliased environmental states and assigns their handling to created subordinate XCS classifier systems. PSXCS uses a history-window approach, but with novel efficiency since the subordinate XCSs, which employ the windows, are only spawned for parts of the state space that are actually aliased. However, because the window lengths are finite and set manually, PSXCS may fail to be optimal in difficult test mazes. This paper introduces Recursive PSXCS (RPSXCS) that automatically spawns windows wherever more history is required. Experimental results show that RPSXCS is both more powerful and learns faster than PSXCS. The present research suggests new potential for history approaches to partially observable environments.
  3. Structured Occurrence Nets: A Formalism for Aiding System Failure Prevention and Analysis Techniques
    Maciej Koutny and Brian Randell 41-91
    This paper introduces the concept of a `structured occurrence net', which as its name indicates is based on that of an `occurrence net', a well-established formalism for an abstract record that represents causality and concurrency information concerning a single execution of a system. Structured occurrence nets consist of multiple occurrence nets, associated together by means of various types of relationship, and are intended for recording or predicting, either the actual behaviour of complex systems as they communicate and evolve, or evidence that is being gathered and analysed concerning their alleged past behaviour. We provide a formal basis for the new formalism and show how it can be used to gain better understanding of complex fault-error-failure chains (i) among co-existing communicating systems, (ii) between systems and their sub-systems, and (iii) involving systems that are controlling, creating or modifying other systems. We then go on to discuss how, with appropriate tools support, perhaps using extended versions of existing tools, structured occurrence nets could form a basis for improved techniques of system failure prevention and analysis.
  4. An Effective Message Embedding Scheme for 3D Models
    Meng-Tsan Li, Nien-Ching Huang,  Kuo-Chen Wu,  Chin-Kai Jan,  Chung-Ming Wang 93-109
    We present an effective message embedding scheme for 3D models. We propose the unit length as the quantizer to generate an embedding order list and an embedding index list. Our scheme considers every two elements in the embedding order list as the order pair, and we embed 3 bits of 0 or 1 secret message into the index pair associated with the order pair. The message embedding is effective requiring, at most, adding 1 to, or subtracting 1 from, the index pair. This reflects a slight perturbation of a points coordinates where the magnitude of the perturbation is no greater than one unit length. Our algorithm achieves a high embedding capacity, being 4.5 times the number of points in the point cloud models. This amount of capacity allows us to convey a 502x502 resolution of the black-and-white image into a point cloud model consisting of 56,194 points for covert communication. The capacity magnitude is 50%-75%higher than that of the current state-of-the-art algorithms, yet the model distortion due to the message embedding is smaller than that of our counterparts. Our algorithm is robust against translation, rotation, and uniformly scaling operations. It is fast, simple to implement, and the message can be extracted without referring to the original point cloud model. We believe our scheme is appropriate for most point cloud models.
  5. Expressiveness of Petri Nets with Stopwatches. Dense-time Part
    Morgan Magnin,  Pierre Molinaro,  Olivier (H.) Roux 111-138
    With this contribution, we aim to draw a comprehensive classification of Petri nets with stopwatches w.r.t. expressiveness and decidability issues. This topic is too ambitious to be summarized in a single paper. That is why we present our results in two different parts. The scope of this first paper is to address the general results that apply for both dense-time and discrete-time semantics. We study the class of bounded Petri nets with stopwatches and reset arcs (rSwPNs), which is an extension of T-time Petri nets (TPNs) where time is associated with transitions. Stopwatches can be reset, stopped and started. We give the formal dense-time and discrete-time semantics of these models in terms of Transition Systems. We study the expressiveness of rSwPNs and its subclasses w.r.t. (weak) bisimilarity (behavioral semantics). The main results are following: 1) bounded rSwPNs and 1-safe rSwPNs are equally expressive; 2) For all models, reset arcs add expressiveness. 3) The resulting partial classification of models is given by a set of relations explained in Fig. 7: in the forthcoming paper, we will complete these results by covering expressiveness and decidability issues when discrete-time nets are considered. For the sake of simplicity, our results are explained on a model such that the stopwatches behaviors are expressed using inhibitor arcs. Our conclusions can however be easily extended to the general class of Stopwatch Petri nets.
  6. Expressiveness of Petri Nets with Stopwatches. Discrete-time Part
    Morgan Magnin,  Pierre Molinaro,  Olivier (H.) Roux 139-176
    With this contribution, we aim to draw a comprehensive classification of Petri nets with stopwatches w.r.t. expressiveness and decidability issues. This topic is too ambitious to be summarized in a single paper. That is why we present our results in two different parts. In the first part of our work, we established new results regarding to both dense-time and discrete-time semantics. We now focus on the discrete-time specificities. We address the class of bounded Petri nets with stopwatches and reset arcs (rSwPNs), which is an extension of T-time Petri nets (TPNs) where time is associated with transitions. Stopwatches can be reset, stopped and started. We recall the formal dense-time and discrete-time semantics of these models in terms of Transition Systems. We study the expressiveness of rSwPNs and its subclasses w.r.t. (weak) bisimilarity (behavioral semantics). The main results are following: 1) Discrete-time bounded TPNs, discrete-time bounded rSwPNs and untimed Petri nets are equally expressive; 2) The resulting (final) classification of models is given by a set of relations explained in Fig. 7. While investigating expressiveness, we exhibit proofs that can be easily extended to the resolution of decidability issues. Among other results, we prove that, for bounded rSwPNs, the state and marking reachability problems - undecidable with dense-time semantics - are decidable when discrete-time is considered. Table 1 gives a synthesis of the main decidability results for these models. For the sake of simplicity, our results are explained on a model such that the stopwatches behaviors are expressed using inhibitor arcs. Our conclusions can however be easily extended to the general class of Stopwatch Petri nets.
  7. Algebraic Semantics of Similarity-Based Bitten Rough Set Theory
    A. Mani 177-197
    We develop two algebraic semantics for bitten rough set theory ([19]) over similarity spaces and their abstract granular versions. Connections with choice based generalized rough semantics developed in [15] by the present author and general cover based rough set theories are also considered.
  8. MR Brain Image Segmentation Using A Multi-seed Based Automatic Clustering Technique
    Sriparna Saha and Sanghamitra Bandyopadhyay 199-214
    In this paper, the automatic segmentation of multispectral magnetic resonance image of the brain is posed as a clustering problem in the intensity space. Thereafter an automatic clustering technique is proposed to solve this problem. The proposed real-coded variable string length genetic clustering technique (MCVGAPS clustering) is able to evolve the number of clusters present in the data set automatically. Each cluster is divided into several small hyperspherical subclusters and the centers of all these small sub-clusters are encoded in a string to represent the whole clustering. For assigning points to different clusters, these local sub-clusters are considered individually. For the purpose of objective function evaluation, these sub-clusters are merged appropriately to form a variable number of global clusters. A recently developed point symmetry distance based cluster validity index, Sym-index, is optimized to automatically evolve the appropriate number of clusters present in an MR brain image. The proposed method is applied on several simulated T1-weighted, T2-weighted and proton density normal and MS lesion magnetic resonance brain images. Superiority of the proposed method over Fuzzy C-means, Expectation Maximization clustering algorithms are demonstrated quantitatively. The automatic segmentation obtained by multiseed based multiobjective clustering technique (MCVGAPS) is also compared with the available ground truth information.
  9. Tensor Framework and Combined Symmetry for Hypertext Mining
    Suman Saha,  C.A. Murthy  and  Sankar K. Pal, 215-234
    We have made a case here for utilizing tensor framework for hypertext mining. Tensor is a generalization of vector and tensor framework discussed here is a generalization of vector space model which is widely used in the information retrieval and web mining literature. Most hypertext documents have an inherent internal tag structure and external link structure that render the desirable use of multidimensional representations such as those offered by tensor objects. We have focused on the advantages of Tensor Space Model, in which documents are represented using sixth-order tensors. We have exploited the local-structure and neighborhood recommendation encapsulated by the proposed representation. We have defined a similarity measure for tensor objects corresponding to hypertext documents, and evaluated the proposed measure for mining tasks. The superior performance of the proposed methodology for clustering and classification tasks of hypertext documents have been demonstrated here. The experiment using different types of similarity measure in the different components of hypertext documents provides the main advantage of the proposed model. It has been shown theoretically that, the computational complexity of an algorithm performing on tensor framework using tensor similarity measure as distance is at most the computational complexity of the same algorithm performing on vector space model using vector similarity measure as distance.
  10. An Algebraic Framework for Defining Behaviours of Concurrent Systems. Part 1: The Constructive Presentation
    Józef Winkowski 235-273
    The paper is the first part of a two-part paper that contributes with a concept of a process viewed as a model of a run of a phenomenon (discrete, continuous, or of a mixed type), with operations allowing to define complex processes in terms of their components, with the respective algebras, and with the idea of using the formal tools thus obtained to describe the behaviours of concurrent systems.
    A process may have an initial state (a source), a final state (a target), or both. A process can be represented by a partially ordered multiset. Processes of which one can be a continuation of the other can be composed sequentially. Independent processes, i.e. processes which do not disturb each other, can be composed in parallel. Processes may be prefixes, i.e. independent components of initial segments of other processes.
    Processes in a universe of objects and operations on such processes form a partial algebra, called algebra of processes. Algebras of processes are partial categories with respect to the sequential composition, and partial monoids with respect to the parallel composition.
    Algebras of processes can be used to define behaviours of concurrent systems. The behaviour of a system can be defined as the set of possible processes of this system with a structure on this set. Such a set is prefix-closed. The structure on this set reflects the prefix order and, possibly, specific features of the behaviour like observability, the relation to flow of real time, etc.
    Algebras of processes can also be used to define behaviours, to define operations on behaviours similar to those in the existing calculi of behaviours, and to define random behaviours.
    The first part of the whole paper investigates algebras of processes and their applications to describing behaviours of systems. In the second part the properties of algebras of processes described in the first part are regarded as axioms defining a class of abstract partial algebras, called behaviour-oriented algebras, and they initiate a theory of such algebras.
  11. Homogeneous Spiking Neural P Systems
    Xiangxiang Zeng,  Xingyi Zhang,  Linqiang Pan 275-294
    Spiking neural P systems are a class of distributed parallel computing models inspired from the way the neurons communicate with each other by means of electrical impulses (called "spikes"). In this paper, we consider a restricted variant of spiking neural P systems, called homogeneous spiking neural P systems, where each neuron has the same set of rules. The universality of homogeneous spiking neural P systems is investigated. One of universality results is that it is sufficient for homogeneous spiking neural P system to have only one neuron that behaves non-deterministically in order to achieve Turing completeness.
  12.  

97 (3) 2009


  1. Special Issue on Stringology. Preface i-ii
  2. Combinatorics of Unique Maximal Factorization Families (UMFFs)
    David E. Daykin, Jacqueline W. Daykin,  W.F. (Bill) Smyth 295-309
    Suppose a set W of strings contains exactly one rotation (cyclic shift) of every primitive string on some alphabet S. Then W is a circ-UMFF if and only if every word in S+ has a unique maximal factorization over W. The classic circ-UMFF is the set of Lyndon words based on lexicographic ordering (1958). Duval (1983) designed a linear sequential Lyndon factorization algorithm; a corresponding PRAM parallel algorithm was described by J. Daykin, Iliopoulos and Smyth (1994). Daykin and Daykin defined new circ-UMFFs based on various methods for totally ordering sets of strings (2003), and further described the structure of all circ-UMFFs (2008). Here we prove new combinatorial results for circ-UMFFs, and in particular for the case of Lyndon words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of our results in terms of dictionaries. Applications of circ-UMFFs pertain to structured methods for concatenating and factoring strings over ordered alphabets, and those of Lyndon words are wide ranging and multidisciplinary.
  3. Faster Algorithms for Computing Maximal Multirepeats in Multiple Sequences
    Costas S. Iliopoulos,  W.F. Smyth,  Munina Yusufu 311-320
    A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat is a repeat that occurs at least mmin times (mmin ³ 2) in each of at least q ³ 1 strings in a given set of strings. In this paper, we describe a family of efficient algorithms based on suffix arrays to compute maximal multirepeats under various constraints. Our algorithms are faster, more flexible and much more space-efficient than algorithms recently proposed for this problem. The results extend recent work by two of the authors computing all maximal repeats in a single string.
  4. A New Algorithm for Building Alphabetic Minimax Trees
    Travis Gagie 321-329
    We show how to build an alphabetic minimax tree for a sequence W = w1, ¼, wn of real weights in O (n d loglogn) time, where d is the number of distinct integers éwi ù. We apply this algorithm to building an alphabetic prefix code given a sample.
  5. Toward a General Framework for Polyphonic Comparison 1
    Julien Allali,  Pascal Ferraro,  Pierre Hanna,  Costas Iliopoulos,  Matthias Robine 331-346
    Existing symbolic music comparison systems generally consider monophonic music or monophonic reduction of polyphonic music. Adaptation of alignment algorithms to music leads to accurate systems, but their extensions to polyphonic music raise new problems. Indeed, a chord may match several consecutive notes, or the difference between two similar motifs may be a few swapped notes. Moreover, the substitution scores between chords are difficult to set up. In this paper, we propose a general framework for polyphonic music using the substitution score scheme set for monophonic music, which allows new operations by extending the operations proposed by Mongeau and Sankoff [15]. From a practical point of view, the limitation of chord sizes and the number of notes that can be merged consecutively lead to a complexity that remains quadratic.

97 (4) 2009


  1. Complex Algebras of Arithmetic
    Ivo Düntsch,  Ian Pratt-Hartmann 347-367
    An arithmetic circuit is a labeled, acyclic directed graph specifying a sequence of arithmetic and logical operations to be performed on sets of natural numbers. Arithmetic circuits can also be viewed as the elements of the smallest subalgebra of the complex algebra of the semiring of natural numbers. In the present paper we investigate the algebraic structure of complex algebras of natural numbers and make some observations regarding the complexity of various theories of such algebras.
  2. An Image Authentication Based on Discrete Fourier Transform
    The Duc Kieu,  Chin-Chen Chang 369-379
    The advances of network technologies and digital devices facilitate users to exchange multimedia data over the public networks. However, this also raises significant concerns about how to protect sensitive multimedia data from being illegally copied and unauthorized modifications. Thus, this paper proposes a fragile watermarking method to detect illegitimate alterations of the watermarked data. The proposed method embeds a grayscale watermark image into a grayscale cover image in a block-by-block manner by using discrete Fourier transform. Experimental results show that the proposed method can successfully and exactly detect and localize any tampered regions of the watermarked image.
  3. Data Clustering Using Multi-objective Differential Evolution Algorithms
    Kaushik Suresh, Debarati Kundu, Sayan Ghosh, Swagatam Das, Ajith Abraham 381-403
    The article considers the task of fuzzy clustering in a multi-objective optimization (MO) framework. It compares the relative performance of four recently developed multi-objective variants of Differential Evolution (DE) on over the fuzzy clustering problem, where two conflicting fuzzy validity indices are simultaneously optimized. The resultant Pareto optimal set of solutions from each algorithm consists of a number of non-dominated solutions, from which the user can choose the most promising ones according to the problem specifications. A real-coded representation for the candidates is used for DE. A comparative study of four DE variants with two most well-known MO clustering techniques, namely the NSGA II (Non Dominated Sorting GA) and MOCK (Multi-Objective Clustering with an unknown number of clusters K) is also undertaken. Experimental results reported for six artificial and four real life datasets (including a microarray dataset of budding yeast) of varying range of complexities indicates that DE can serve as a promising algorithm for devising MO clustering techniques.
  4. Modeling and Reasoning with Paraconsistent Rough Sets
    Aida Vitória,  Jan Małuszyński,  Andrzej Szałas 405-438
    We present a language for defining paraconsistent rough sets and reasoning about them. Our framework relates and brings together two major fields: rough sets [23] and paraconsistent logic programming [9]. To model inconsistent and incomplete information we use a four-valued logic.
    The language discussed in this paper is based on ideas of our previous work [21, 32, 22] developing a four-valued framework for rough sets. In this approach membership function, set containment and set operations are four-valued, where logical values are (true), (false), i (inconsistent) and u(unknown).
    We investigate properties of paraconsistent rough sets as well as develop a paraconsistent rule language, providing basic computational machinery for our approach.
  5. An Algebraic Framework for Defining Behaviours of Concurrent Systems. Part 2: The Axiomatic Presentation
    Józef Winkowski 439-524
    The paper is the second part of two-part paper that contributes with a concept of a process, with operations allowing to define complex processes in terms of their components, with the respective algebras, and with the idea of using the formal tools thus obtained to describe the behaviours of concurrent systems.
    In the first part a universal model of a process have been introduced and operations on processes have been defined.
    A process is viewed as a model of a run of a system (discrete, continuous, or of a mixed type). A process may have an initial state (a source), a final state (a target), or both. A process can be represented by a partially ordered multiset. Processes of which one is a continuation of the other can be composed sequentially. Independent processes, can be composed in parallel. Processes may be prefixes, i.e. independent components of initial segments of other processes.
    It has been shown that processes in a universe of objects and operations on such processes form a partial algebra, called algebra of processes, that is a specific partial category with respect to the sequential composition, and a specific partial monoid with respect to the parallel composition.
    In the second part the properties of algebras of processes described in the first part are regarded as axioms defining a class of abstract partial algebras, called behaviour-oriented algebras, and properties of such algebras are investigated. In particular, it is shown how some of the behaviour-oriented algebras can be represented as algebras of processes, and how to use them to describe phenomena with states and processes provided with specific structures.
  6. An Interval-Valued Intuitionistic Fuzzy Rough Set Model
    Zhiming Zhang 525-552
    Given a widespread interest in rough sets as being applied to various tasks of data analysis it is not surprising at all that we have witnessed a wave of further generalizations and algorithmic enhancements of this original concept. This paper proposes an interval-valued intuitionistic fuzzy rough model by means of integrating the classical Pawlak rough set theory with the interval-valued intuitionistic fuzzy set theory. Firstly, some concepts and properties of interval-valued intuitionistic fuzzy set and interval-valued intuitionistic fuzzy relation are introduced. Secondly, a pair of lower and upper interval-valued intuitionistic fuzzy rough approximation operators induced from an interval-valued intuitionistic fuzzy relation is defined, and some properties of approximation operators are investigated in detail. Furthermore, by introducing cut sets of interval-valued intuitionistic fuzzy sets, classical representations of interval-valued intuitionistic fuzzy rough approximation operators are presented. Finally, the connections between special interval-valued intuitionistic fuzzy relations and interval-valued intuitionistic fuzzy rough approximation operators are constructed, and the relationships of this model and the others rough set models are also examined.