Fundamenta Informaticae - Volume 97, issue 1-2

Authors: Diqun, Yan | Rangding, Wang | Liguang, Zhang

Article Type: Research Article

Abstract: 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. Show more

Keywords: Steganography, MP3, quantization, Huffman coding

DOI: 10.3233/FI-2009-190

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 1-14, 2009

Authors: Hamzeh, Ali | Hashemi, Sattar | Sami, Ashkan | Rahmani, Adel

Article Type: Research Article

Abstract: 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 subordinateXCSs, 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. Show more

Keywords: Learning Classifier Systems, Partially Observable Environments, XCS, CSXCS

DOI: 10.3233/FI-2009-191

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 15-40, 2009

Authors: Koutny, Maciej | Randell, Brian

Article Type: Research Article

Abstract: 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 ormodifying 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. Show more

Keywords: failures, errors, faults, dependability, judgement, occurrence nets, abstraction, formal analysis

DOI: 10.3233/FI-2009-192

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 41-91, 2009

Authors: Li, Meng-Tsan | Huang, Nien-Ching | Wu, Kuo-Chen | Jan, Chin-Kai | Wang, Chung-Ming

Article Type: Research Article

Abstract: 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-ofthe- 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. Show more

Keywords: Message embedding, 3D models, quantization, information hiding, steganography

DOI: 10.3233/FI-2009-193

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 93-109, 2009

Authors: Magnin., Morgan | Molinaro, Pierre | Roux, Olivier (H.)

Article Type: Research Article

Abstract: 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 rSw- PNs 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. Show more

Keywords: real-time systems, time Petri nets, Petri nets with stopwatches, expressiveness

DOI: 10.3233/FI-2009-194

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 111-138, 2009

Authors: Magnin, Morgan | Molinaro, Pierre | Roux, Olivier (H.)

Article Type: Research Article

Abstract: 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. Show more

Keywords: real-time systems, time Petri nets, discrete-time semantics, Petri nets with stopwatches, expressiveness, decidability

DOI: 10.3233/FI-2009-195

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 139-176, 2009

Authors: Mani, A.

Article Type: Research Article

Abstract: 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.

Keywords: Rough Set Theory over Tolerance Approximation Spaces, Bitten Rough Semantics, Granular Rough Semantics, λ-Rough Algebras, Discernibility in Similarity Spaces

DOI: 10.3233/FI-2009-196

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 177-197, 2009

Authors: Saha, Sriparna | Bandyopadhyay, Sanghamitra

Article Type: Research Article

Abstract: 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. Show more

Keywords: Clustering, multi-seed, symmetry, cluster validity indices, magnetic resonance image

DOI: 10.3233/FI-2009-197

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 199-214, 2009

Authors: Saha, Suman | Murthy, C.A. | Pal, Sankar K.

Article Type: Research Article

Abstract: 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 algorithmperforming on vector space model using vector similarity measure as distance. Show more

Keywords: tensor space, hypertext, internal structure, similarity measure

DOI: 10.3233/FI-2009-198

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 215-234, 2009

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: 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 behaviouroriented algebras, and they initiate a theory of such algebras. Show more

Keywords: Process, state, sequential composition, parallel composition, category, partial category, partial monoid, independence, structure, behaviour, random behaviour

DOI: 10.3233/FI-2009-199

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 235-273, 2009

Authors: Zeng, Xiangxiang | Zhang, Xingyi | Pan, Linqiang

Article Type: Research Article

Abstract: 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. Show more

Keywords: Membrane computing, Spiking neural P system, Register machine

DOI: 10.3233/FI-2009-200

Citation: Fundamenta Informaticae, vol. 97, no. 1-2, pp. 275-294, 2009