Fundamenta Informaticae - Volume 82, issue 1-2

Authors: Chang, Chin-Chen | Lin, Chih-Yang | Hsieh, Yi-Pei

Article Type: Research Article

Abstract: Hiding Data in a cover image often applies a steganographic technique that makes the stego image appear as similar to the original cover image as possible. Conventional VQ-based (vector quantization) steganographic methods typically involve codeword replacements to hide secret bits. Such replacements may cause serious distortion or a perceptible block effect on the stego image. In this paper, we propose a three-phase steganographic method for the VQ index table. Instead of applying codeword replacements, the …proposedmethod uses different coding schemes-SOC, SMVQ, and VQ-to imply the secret bits. The quality of the stego image generated by the proposed method is completely equal to that of the original cover image (i.e., the VQ cover image). Experimental results have shown that the proposed method has the best stego image quality compared with other methods. In addition, the proposed method provides adaptive embedding capacity and compression bit rate according to predefined thresholds. Show more

Keywords: Steganography, search-order coding (SOC), side match vector quantization (SMVQ)

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 1-13, 2008

Authors: Chiang, Yung-Kuei | Tsai, Piyu | Huang, Feng-Long

Article Type: Research Article

Abstract: The practice of concealing secret messages into index-based images has generally suffered from problems of image quality degradation and hiding capacity restriction. A steganographic scheme using an improved codebook partition is proposed in this paper. The proposed scheme partitions the codebook into different member sub-clusters in terms of their similarity between the codewords for increasing the hiding capacity and reducing the image distortion. Any size of a subcluster was allowed in the proposed scheme, so as …to improve the traditional approaches in which the size of a sub-cluster was restricted to the power of two. As a result of this revised scheme, an increased hiding capacity and a reduction in image distortion are obtained, as indicated from experimental results. The average performance of the proposed scheme is superior to that of those standard methods. Show more

Keywords: index-based image, information hiding, steganography

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 15-27, 2008

Authors: Csuhaj-Varjú, Erzsébet | Nola, Antonio Di | Păun, Gheorghe | Pérez-Jiménez, Mario J. | Vaszil, György

Article Type: Research Article

Abstract: This paper proposes and investigates the possibility of transforming a configuration of a P system (the membrane structure and the multisets of symbol-objects present in the compartments) into another configuration by means of a given set of rules to be applied to the membranes and to the multisets of objects. Although this transformation is obtained during the computation in a P system, we consider it as a goal per se, as a pre-computation phase, when the …system itself is built. In this framework, several important problems appear: the edit-distance between configurations (with respect to a given set of editing rules), normal forms, the reachability of configurations, or the existence of single configurations from which a given family of configurations can be constructed, only to mention a few. We investigate here some of these questions; the paper is mainly devoted to formulating problems in the new framework, to calling attention to the possible extensions and the usefulness of the present approach. Show more

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 29-46, 2008

Authors: Drewes, Frank | van der Merwe, Brink

Article Type: Research Article

Abstract: The path languages of random permitting context tree languages are investigated. The main result is that these path languages are regular. This confirms a previous conjecture.

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 47-60, 2008

Authors: Ésik, Zoltán | Iván, Szabolcs

Article Type: Research Article

Abstract: We introduce the notion of the Moore product of tree automata as a special case of the cascade product. We give an algebraic characterization of the expressive power of certain CTL-like temporal logics based on the notion of varieties of finite tree automata closed under the Moore product.

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 61-78, 2008

Authors: Ésik, Zoltán | Iván, Szabolcs

Article Type: Research Article

Abstract: We provide structural descriptions of certain varieties of finite tree automata closed under a version of the cascade product, called the Moore product. As a byproduct, we obtain decidable characterizations of the expressive power of certain fragments of CTL on finite trees.

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 79-103, 2008

Authors: Galiński, Grzegorz | Skarbek, Władysław

Article Type: Research Article

Abstract: In this paper, the use of the Dominant Color descriptor, one of the visual descriptors defined in MPEG-7 standard for image indexing and search, is discussed. Various similarity functions for matching the descriptors are presented. Next, the concept of dominant colors cumulative distribution function (CDF) is introduced and a new distance function for the descriptors matching is also proposed. The function is equivalent to the computing volume of space bounded by two dominant colors CDFs. Efficient …algorithm for computing CDF-based distance which uses the properties of discrete CDF function, is also presented. Finally, various dominant colors matching methods are compared in a similarity image search scenario consisting of 'query-by-example' nearest neighbours search, and the experimental results are presented and discussed. Show more

Keywords: image search, particle ensembles, dominant colors, MPEG-7

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 105-112, 2008

Authors: Ilcinkas, David | Pelc, Andrzej

Article Type: Research Article

Abstract: The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. …Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game. Show more

Keywords: Selfish agent, Nash equilibrium, asynchronous game

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 113-125, 2008

Authors: Kaminski, Michael

Article Type: Research Article

Abstract: We show that a stutter-invariant property is expressible in propositional temporal logic without the "until" operator if and only if it is expressible in the Generalized Temporal Logic of Actions.

Keywords: Propositional temporal logic, temporal interpretations, invariance under stuttering

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 127-140, 2008

Authors: Kučera, Antonín | Stražovský, Oldřich

Article Type: Research Article

Abstract: We study the problem of effective controller synthesis for finite-state Markov decision processes (MDPs) and the class of properties definable in the logic PCTL extended with long-run average propositions. We show that the existence of such a controller is decidable, and we give an algorithm which computes the controller if it exists. We also address the issue of "controller robustness", i.e., the problem whether there is a controller which still guarantees the satisfaction of a given …property when the probabilities in the considered MDP slightly deviate from their original values. From a practical point of view, this is an important aspect since the probabilities are often determined empirically and hence they are inherently imprecise. We show that the existence of robust controllers is also decidable, and that such controllers are effectively computable if they exist. Show more

Keywords: controller synthesis, Markov decision process, PCTL

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 141-153, 2008

Authors: Lin, Ching-Chiuan | Hsueh, Nien-Lin | Shen, Wen-Hsiang

Article Type: Research Article

Abstract: This paper proposes a high-performance reversible data hiding algorithm based on the block difference histogram of a cover image. If a message is to be embedded into an image, the difference of the block at the maximum point is increased by 1 or left unchanged if the message bit is "1" or "0", respectively. Experimental results show that the average payload capacity of the test images can be up to 1.52 bits per pixel (bpp). Average …payload and pure payload capacities for PSNR⩾30 dB can be up to 1.13 bpp and 1.06 bpp, respectively. Moreover, the original cover image can be recovered without any distortion and the implementation of the proposed algorithm is very easy. Show more

Keywords: Reversible data hiding, lossless watermark, steganography

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 155-169, 2008

Authors: Moura, Arnaldo V. | Pinto, Guilherme A.

Article Type: Research Article

Abstract: Universality for deterministic Timed Büchi Automata (TBA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TBA is Π^1_1 -hard and its precise position in the analytical hierarchy is still an open question. In this paper we introduce two types of syntactical restrictions to nondeterministic TBA, which are of independent interest, and show that their universality problem is Π^1_1 -complete. These restrictions define, …as we prove, proper subclasses of the class of timed languages defined by nondeterministic TBA. This suggests, as we argue, that no solution to that open question will come without surprise. We also establish closure properties and the relationships between the classes of languages we describe. Show more

Keywords: Timed Automata, Universality, Analytical Hierarchy

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 171-184, 2008

Authors: Terlikowski, Tomasz

Article Type: Research Article

Abstract: We introduce the notion of information in a two-stage decision process. We begin by examining the general scheme of a two-stage control problem. The final aim is to give a precise, formal definition of what we mean as information within a decision process.

Keywords: two-stage decision process, variant, informational relation, team, canonical team, objective information, deterministic information

Citation: Fundamenta Informaticae, vol. 82, no. 1-2, pp. 185-212, 2008