97 (12) 2009
 Quantization Step Paritybased Steganography for MP3 Audio
Yan Diqun, Wang Rangding, Zhang Liguang 114
Petitcolas has proposed a steganographic technique called MP3Stego which can
hide secret messages in a MP3 audio. This technique is wellknown 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.
 A Recursive Classifier System for Partially Observable Environments
Ali Hamzeh, Sattar Hashemi, Ashkan Sami, Adel Rahmani 1540
Previously we introduced Parallel Specialized XCS (PSXCS), a distributedarchitecture classifier system
that detects aliased environmental states and assigns their handling to created subordinate XCS classifier
systems. PSXCS uses a historywindow 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.
 Structured Occurrence Nets: A Formalism for Aiding System
Failure Prevention and Analysis Techniques
Maciej Koutny and Brian Randell 4191
This paper introduces the concept of a `structured occurrence
net', which as its name indicates is based on that of an `occurrence
net', a wellestablished 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 faulterrorfailure chains (i) among coexisting
communicating systems, (ii) between systems and their subsystems, 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.
 An Effective Message Embedding Scheme for 3D Models
MengTsan Li, NienChing Huang, KuoChen Wu, ChinKai Jan, ChungMing Wang 93109
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 blackandwhite 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 stateoftheart 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.
 Expressiveness of Petri Nets with Stopwatches. Densetime Part
Morgan Magnin, Pierre Molinaro, Olivier (H.) Roux 111138
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 densetime and discretetime semantics. We study the class of bounded Petri nets with stopwatches and reset arcs (rSwPNs), which is an extension of Ttime Petri nets (TPNs) where time is associated with transitions. Stopwatches can be reset, stopped and started.
We give the formal densetime and discretetime 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 1safe 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 discretetime 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.
 Expressiveness of Petri Nets with Stopwatches. Discretetime Part
Morgan Magnin, Pierre Molinaro, Olivier (H.) Roux 139176
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 densetime and discretetime semantics. We now focus on the discretetime specificities. We address the class of bounded Petri nets with stopwatches and reset arcs (rSwPNs), which is an extension of Ttime Petri nets (TPNs) where time is associated with transitions. Stopwatches can be reset, stopped and started.
We recall the formal densetime and discretetime 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) Discretetime bounded TPNs, discretetime 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 densetime semantics  are decidable when discretetime 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.
 Algebraic Semantics of SimilarityBased Bitten Rough Set Theory
A. Mani 177197
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.
 MR Brain Image Segmentation Using A Multiseed
Based Automatic Clustering Technique
Sriparna Saha and Sanghamitra Bandyopadhyay 199214
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 realcoded 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 subclusters are encoded in a string to represent
the whole clustering. For assigning points to different clusters, these local subclusters are considered individually.
For the purpose of objective function evaluation, these subclusters are merged appropriately to form a variable
number of global clusters.
A recently developed point symmetry distance
based cluster validity index, Symindex, is optimized
to automatically evolve the appropriate
number of clusters present in an MR brain image. The proposed
method is applied on several simulated T1weighted, T2weighted
and proton density normal and MS lesion magnetic resonance brain images. Superiority of the
proposed method over Fuzzy Cmeans, 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.
 Tensor Framework and Combined Symmetry for Hypertext Mining
Suman Saha, C.A. Murthy and Sankar K. Pal, 215234
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 sixthorder tensors. We have exploited
the localstructure 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.
 An Algebraic Framework for Defining Behaviours of Concurrent Systems.
Part 1: The Constructive Presentation
Józef Winkowski 235273
The paper is the first part of a twopart 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 prefixclosed.
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 behaviouroriented algebras, and they initiate a theory of such algebras.
 Homogeneous Spiking Neural P Systems
Xiangxiang Zeng, Xingyi Zhang, Linqiang Pan 275294
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 nondeterministically in order to achieve
Turing completeness.

97 (3) 2009
 Special Issue on Stringology. Preface iii
 Combinatorics of Unique Maximal Factorization Families (UMFFs)
David E. Daykin, Jacqueline W. Daykin, W.F. (Bill) Smyth 295309
Suppose a set W of strings contains exactly one rotation
(cyclic shift) of every primitive string on some alphabet S.
Then W is a circUMFF if and only if every
word in S^{+} has a unique maximal factorization over W. The
classic circUMFF 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 circUMFFs based on various methods for totally ordering sets of strings (2003),
and further described the structure of all circUMFFs (2008).
Here we prove new combinatorial results for circUMFFs, and in particular for the
case of Lyndon words. We introduce Acrobat and Flight Deck circUMFFs, and describe some of our
results in terms of dictionaries.
Applications of circUMFFs pertain to structured methods for concatenating and
factoring strings over ordered alphabets, and those of Lyndon words are wide ranging
and multidisciplinary.
 Faster Algorithms for Computing Maximal Multirepeats in Multiple Sequences
Costas S. Iliopoulos, W.F. Smyth, Munina Yusufu 311320
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 m_{min} times (m_{min} ³ 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 spaceefficient 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.
 A New Algorithm for Building Alphabetic Minimax Trees
Travis Gagie 321329
We show how to build an alphabetic minimax tree for a sequence
W = w_{1}, ¼, w_{n} of real weights in O (n d loglogn)
time, where d is the number of distinct integers éw_{i} ù.
We apply this algorithm to building an alphabetic prefix code given a sample.
 Toward a General Framework for Polyphonic Comparison ^{1}
Julien Allali, Pascal Ferraro, Pierre Hanna,
Costas Iliopoulos, Matthias Robine 331346
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
 Complex Algebras of Arithmetic
Ivo Düntsch, Ian PrattHartmann 347367
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.
 An Image Authentication Based on Discrete Fourier Transform
The Duc Kieu, ChinChen Chang 369379
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 blockbyblock 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.
 Data Clustering Using Multiobjective Differential Evolution Algorithms
Kaushik Suresh, Debarati Kundu, Sayan Ghosh, Swagatam Das,
Ajith Abraham 381403
The article considers the task of fuzzy clustering in a
multiobjective optimization (MO) framework. It compares the
relative performance of four recently developed multiobjective
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 nondominated
solutions, from which the user can choose the most promising ones
according to the problem specifications. A realcoded representation
for the candidates is used for DE. A comparative study of four DE
variants with two most wellknown MO clustering techniques, namely
the NSGA II (Non Dominated Sorting GA) and MOCK (MultiObjective
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.
 Modeling and Reasoning with Paraconsistent Rough Sets
Aida Vitória, Jan Małuszyński, Andrzej Szałas 405438
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 fourvalued logic.
The language discussed in this paper is based on ideas of our previous work
[21, 32, 22] developing a fourvalued framework for rough sets.
In this approach membership function, set containment and set operations are
fourvalued, 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.
 An Algebraic Framework for Defining Behaviours of Concurrent Systems.
Part 2: The Axiomatic Presentation
Józef Winkowski 439524
The paper is the second part of twopart 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 behaviouroriented algebras, and properties of such algebras are
investigated. In particular, it is shown how some of the behaviouroriented algebras can be represented as algebras of
processes, and how to use them to describe phenomena with states and processes provided with specific structures.
 An IntervalValued Intuitionistic Fuzzy Rough Set Model
Zhiming Zhang 525552
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 intervalvalued intuitionistic fuzzy rough model by means of integrating the classical Pawlak rough set theory with the intervalvalued intuitionistic fuzzy set theory. Firstly, some concepts and properties of intervalvalued intuitionistic fuzzy set and intervalvalued intuitionistic fuzzy relation are introduced. Secondly, a pair of lower and upper intervalvalued intuitionistic fuzzy rough approximation operators induced from an intervalvalued intuitionistic fuzzy relation is defined, and some properties of approximation operators are investigated in detail. Furthermore, by introducing cut sets of intervalvalued intuitionistic fuzzy sets, classical representations of intervalvalued intuitionistic fuzzy rough approximation operators are presented. Finally, the connections between special intervalvalued intuitionistic fuzzy relations and intervalvalued intuitionistic fuzzy rough approximation operators are constructed, and the relationships of this model and the others rough set models are also examined.