Fundamenta Informaticae

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties.

Feature selection is an important preprocessing step in pattern analysis and machine learning. The key issue in feature selection is to evaluate quality of candidate features. In this work, we introduce a weighted distance learning algorithm for feature selection via maximizing fuzzy dependency. We maximize fuzzy dependency between features and decision by distance learning and then evaluate the quality of features with the learned weight vector. The features deriving great weights are considered to be useful for classification learning. We test the proposed technique with some classical methods and the experimental results show the proposed algorithm is effective.

We consider the inductive inference model of Gold [15]. Suppose we are given a set of functions that are learnable with certain number of mind changes and errors. What properties of these functions are learnable if we allow fewer number of mind changes or errors? In order to answer this question this paper extends the Inductive Inference model introduced by Gold [15]. Another motivation for this extension is to understand and characterize properties that are learnable for a given set of functions. Our extension considers a wide range of properties of function based on their input-output relationship. Two specific properties of functions are studied in this paper. The first property, which we call modality, explores how the output of a function fluctuates. For example, consider a function that predicts the price of a stock. A brokerage company buys and sells stocks very often in a day for its clients with the intent of maximizing their profit. If the company is able predict the trend of the stock market "reasonably" accurately then it is bound to be very successful. Identification criterion for this property of a function f is called PREX which predicts if f(x) is equal to, less than or greater than f(x+1) for each x.

Next, as opposed to a constant tracking by a brokerage company, an individual investor does not often track dynamic changes in stock values. Instead, the investor would like to move the investment to a less risky option when the investment exceeds or falls below certain threshold. We capture this notion using an identification criterion called TREX that essentially predicts if a function value is at, above, or below a threshold value. Conceptually,modality prediction (i.e., PREX) and threshold prediction (i.e., TREX) are "easier" than EX learning. We show that neither the number of errors nor the number of mind-changes can be reduced when we ease the learning criterion from exact learning to learning modality or threshold. We also prove that PREX and TREX are totally different properties to predict. That is, the strategy for a brokerage company may not be a good strategy for individual investor and vice versa.

High quality performance of image segmentation methods presents one leading priority in design and implementation of image analysis systems. Incorporating the most important image data information into segmentation process has resulted in development of innovative frameworks such as fuzzy systems, rough systems and recently rough – fuzzy systems. Data analysis based on rough and fuzzy systems is designed to apprehend internal data structure in case of incomplete or uncertain information. Rough entropy framework proposed in [12,13] has been dedicated for application in clustering systems, especially for image segmentation systems. We extend that framework into eight distinct rough entropy measures and related clustering algorithms. The introduced solutions are capable of adaptive incorporation of the most important factors that contribute to the relation between data objects and makes possible better understanding of the image structure. In order to prove the relevance of the proposed rough entropy measures, the evaluation of rough entropy segmentations based on the comparison with human segmentations from Berkeley and Weizmann image databases has been presented. At the same time, rough entropy based measures applied in the domain of image segmentation quality evaluation have been compared with standard image segmentation indices. Additionally, rough entropy measures seem to comprehend properly properties validated by different image segmentation quality indices.

In this paper a new model for compression of Laplacian source is given. This model consists of hybrid quantizer whose output levels are coded with Golomb-Rice code. Hybrid quantizer is combination of uniform and nonuniform quantizer, and it can be considered as generalized quantizer, whose special cases are uniform and nonuniformquantizers. We propose new generalized optimal compression function for companding quantizers. Hybrid quantizer has better performances (smaller bit-rate and complexity for the same quality) than both uniform and nonuniformquantizers, because it joins their good characteristics. Also, hybrid quantizer allows great flexibility, because there are many combinations of number of levels in uniform part and in nonuniformpart, which give similar quality. Each of these combinations has different bit-rate and complexity, so we have freedom to choose combination which is the most appropriate for our application, in regard to quality, bit-rate and complexity. We do not have such freedom of choice when we use uniform or nonuniform quantizers. Until now, it has been thought that uniform quantizer is the most appropriate to use with lossless code, but in this paper we show that combination of hybrid quantizer and lossless code gives better performances. As lossless code we use Golomb-Rice code because it is especially suitable for Laplacian source since it gives average bit-rate very close to the entropy and it is easier for implementation than Huffman code. Golomb-Rice code is used in many modern compression standards. Our model can be used for compression of all signals with Laplacian distribution.

Progressive image transmission (PIT) is supported by several encoders such as SPIHT, JPEG2000 and so on. However, few of data hiding scheme for progressive transmission images is designed. In this paper, tree-structure-based data hiding for set partitioning in hierarchical trees (SPIHT) images is proposed. The bit stream of SPIHT multi-stage encoded was structured of tree. The secret image can be progressively embedded into SPIHT bit trees.

Experimental results showed the progressive image data hiding is achieved. The secret image is progressively embedded/extracted in SPIHT encoded images. Furthermore, a higher hiding capacity was provided in an earlier encoding which helped the secret image to be identified earlier. Also, an adaptive hiding capacity could be developed by using different tree structures. In comparison with Tsai et al.'s scheme, the proposed scheme had a higher hiding capacity and a better secret image quality.

At Pairing'07, Matsuo proposed two proxy re-encryption schemes: proxy re-encryption fromCBE to IBE and IBE to IBE. Now both schemes have been standardized by P1363.3workgroup. In this paper, we show that their identity based proxy re-encryption scheme is insecure. We give two attacks to this scheme. The first attack shows that the proxy can re-encrypt any IBE user's ciphertext to be the delegatee's ciphertext. The second attack implies that, if the proxy colludes with any delegatee, the proxy and this delegatee can derive any other IBE user's secret key.

Bipolar synchronization systems (BP-systems) constitute a class of coloured Petri nets, well suited for modelling the control flow of discrete dynamical systems. Every BP-system has an underlying ordinary Petri net, a T-system. It further has a second ordinary net attached, a free-choice system. We prove that a BP-system is safe and live if the T-system and the free-choice system are safe and live and the free-choice system in addition has no frozen tokens. This result is the converse of a theorem of Genrich and Thiagarajan and proves an old conjecture. As a consequence we obtain two results about the existence of safe and live BP-systems with prescribed ordinary Petri nets. For the proof of these theorems we introduce the concept of a morphism between Petri nets as a means of comparing different Petri nets. We then apply the classical theory of free-choice systems.

In order to provide large embedding capacity and to minimize distortion for the stego-image, a steganographic method using multi-pixel differencing is presented in this paper. It takes into consideration four pixels of a block, and the differences between the lowest gray-value pixel and its surrounding pixels are used to determine the degree of smoothness and sharpness for embedding the secret data. If the difference values are large in a block, and the block is located in the sharp area then more data can be embedded. On the other hand, if the block is located in the smooth area less data can be embedded. The multi-pixel differencing method is employed in our scheme. We also propose the pixel-value shifting method to increase the image quality. The experimental results show that our scheme has a large embedding capacity without creating a noticeable distortion.