Fundamenta Informaticae - Volume 84, issue 3-4

Authors: Clark, Alexander | Watkins, Chris

Article Type: Research Article

Abstract: We describe methods of representing strings as real valued vectors or matrices; we show how to integrate two separate lines of enquiry: string kernels, developed in machine learning, and Parikh matrices [8], which have been studied intensively over the last few years as a powerful tool in the study of combinatorics over words. In the field of machine learning, there is widespread use of string kernels, which use analogous mappings into high dimensional feature spaces based …on the occurrences of subwords or factors. In this paper we show how one can use string kernels to construct two alternatives to Parikh matrices, that overcome some of the limitations of the Parikh matrix construction. These are morphisms from the free monoid to rings of real-valued matrices under multiplication: one is based on the subsequence kernel and the other on the gap-weighted string kernel. For the latter kernel we demonstrate that for many values of the gap-weight hyperparameter the resulting morphism is injective. Show more

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 291-303, 2008

Authors: Droste, Manfred | Kuich, Werner | Rahonis, George

Article Type: Research Article

Abstract: We introduce multi-valued Büchi and Muller automata over distributive lattices and a multi-valued MSO logic for infinite words. For this logic, we prove the expressive equivalence of ω-recognizable and MSO-definable infinitary formal power series over distributive lattices with negation function. Then we consider multi-valued Muller tree automata and a multi-valued MSO logic for trees over distributive lattices. For this logic, we establish a version of Rabin's theorem for infinitary tree series.

Keywords: Distributive lattices, multi-valued automata over infinite words and trees, infinitary formal power series, multi-valued MSO logic

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 305-327, 2008

Authors: Hamzeh, Ali | Rahmani, Adel

Article Type: Research Article

Abstract: Reinforcement Learning is a learning paradigm that helps the agent to learn to act optimally in an unknown environment through trial and error. An RL-based agent senses its environmental state, proposes an action, and applies it to the environment. Then a reinforcement signal, called the reward, is sent back from the environment to the agent. The agent is expected to learn how to maximize overall environmental reward through its internal mechanisms. One of the most challenging …issues in the RL area arises as a result of the sensory ability of the agent, when it is not able to sense its current environmental state completely. These environments are called partially observable environments. In these environments, the agent may fail to distinguish the actual environmental state and so may fail to propose the optimal action in particular environmental states. So an extended mechanism must be added to the architecture of the agent to enable it to perform optimally in these environments. On the other hand, one of the most-used approaches to reinforcement learning is the evolutionary learning approach and one of the most-used techniques in this family is learning classifier systems. Learning classifier systems try to evolve state-action-reward mappings to model their current environment through trial and error. In this paper we propose a new architecture for learning classifier systems that is able to perform optimally in partially observable environments. This new architecture uses a novel method to detect aliased states in the environment and disambiguates them through multiple instances of classifier systems that interact with the environment in parallel. This model is applied to some well-known benchmark problems and is compared with some of the best classifier systems proposed for these environments. Our results and detailed discussion show that our approach is one of the best techniques among other learning classifier systems in partially observable environments. Show more

Keywords: Learning Classifier Systems, POMDP Environments, XCS

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 329-351, 2008

Authors: Huang, Hui-Feng | Chang, Chin-Chen

Article Type: Research Article

Abstract: The hierarchical cryptographic key assignment is used to assign cryptographic keys to a set of partially ordered classes so that the user in a higher class can derive the cryptographic key for users in a lower class. However, the existing secure schemes for the cryptographic key assignment in a hierarchy do not consider the situation where a user may be employed for only a period of time. If a user resigned from his position and he premeditatedly …eavesdrops on data transmissions, then he can also decrypt some data to obtain useful messages. Thus, all messages are likely to be compromised throughout the system. In this paper, we propose a new cryptographic key assignment scheme in which the cryptographic keys are generated from the identity number of users. Our aim is to minimize the potential damage over a public network. Therefore, as a user who has resigned from his class premeditatedly eavesdrops on later messages, he cannot decrypt the message with his old keys. Moreover, in the proposed method, the key generation and key derivation are quite simple, and the number of the public/secret parameters for each authenticated user is fixed which differs from most previously proposed schemes. Show more

Keywords: Access control, cryptographic key assignment

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 353-361, 2008

Authors: Ishdorj, Tseren-Onolt | Loos, Remco | Petre, Ion

Article Type: Research Article

Abstract: We investigate here the computational efficiency of gene rearrangement found in ciliates (unicellular organisms). We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, these systems can uniformly solve SAT with time complexity O(n ˙ m) for a Boolean formula of m clauses over n variables.

Keywords: Parallel time complexity, non-determinism, gene assembly in ciliates

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 363-373, 2008

Authors: Kazda, Alexandr

Article Type: Research Article

Abstract: The paper gives a characterisation of the chain relation of a sofic subshift. Every sofic subshift Σ can be described by a labelled graph G. Factorising G in a suitable way we obtain the graph G/≈ that offers insight into some properties of the original subshift. Using G/≈ we describe first the chain relation in Σ, then characterise chain-transitive sofic subshifts, chain-mixing sofic subshifts and finally the attractors of the subshift dynamic system. At the end …we present (straightforward) algorithms deciding chain-transitivity and chain-mixing properties of a sofic subshift and listing all the attractors of the subshift system. Show more

Keywords: Sofic subshift, chain relation, chain-transitivity, chain-mixing, attractor

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 375-390, 2008

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

Article Type: Research Article

Abstract: In this paper, we propose an embedding algorithm, of high visual quality, that can adaptively embed a binary message into an image. The binary message to be embedded is divided into two segments, each of which is then decomposed into n + 1 or n types of sub-messages (where n ⩾ 3 enables each pixel to embed a sub-message), respectively, according to the desired embedding capacity. Embedding is done by leaving the pixel value unchanged or changing it …into one of its n or n − 1 neighboring values according to the type of the sub-message. From the results of this study, each pixel may not embed a fixed number of message bits and the adjustment of the pixel value is minimal, thus the image quality is significantly improved by adaptively decomposing the message into sub-messages and embedding them into the host image. Show more

Keywords: Information hiding, LSB

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 391-402, 2008

Authors: Liu, Yong | Xu, Congfu | Zhang, Qiong | Pan, Yunhe

Article Type: Research Article

Abstract: Rough rule extraction refers to the rule induction method by using rough set theory. Although rough set theory is a powerful mathematical tool in dealing with vagueness and uncertainty in data sets, it is lack of effective rule extracting approach under complex conditions. This paper proposes several algorithms to perform rough rule extraction from data sets with different properties. Firstly, in order to obtain uncertainty rules from inconsistent data, we introduce the concept of confidence factor …into the rule extracting process. Then, an improved incremental rule extracting algorithm is proposed based on the analysis of the incremental data categories. Finally, above algorithms are further extended to perform approximate rule extraction from huge data sets. Preliminary experiment results are encouraging. Show more

Keywords: Rough set, improved discernibility matrix, inconsistent rules, incremental algorithm, approximate rule-extracting

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 403-427, 2008

Authors: Patra, Swarnajyoti | Ghosh, Susmita | Ghosh, Ashish

Article Type: Research Article

Abstract: A context-sensitive change-detection technique based on semi-supervised learning with multilayer perceptron is proposed here. In order to take contextual information into account, input patterns are generated considering each pixel of the difference image along with its neighboring pixels. A heuristic technique is suggested to identify a few initial labeled patterns without using ground truth information. The network is initially trained using these labeled data. The unlabeled patterns are iteratively processed by the …already trained perceptron to obtain a soft class label. Experimental results, carried out on two multispectral and multitemporal remote sensing images, confirm the effectiveness of the proposed approach. Show more

Keywords: Semi-supervised learning, remote-sensing, change-detection, multitemporal images, neural network

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 429-442, 2008

Authors: Ranalter, Kurt

Article Type: Research Article

Abstract: One of the aims of a logic for pragmatics is to provide a logical framework that formalizes reasoning about speech acts. In this paper we investigate the semantics of a fragment of the logic for pragmatics proposed by Bellin and Dalla Pozza in "A pragmatic interpretation of substructural logics" (Feferman Festschrift, ASL Lecture Notes in Logic 15, 2002). The logic deals with acts of assertion and acts of obligation, and it incorporates a rule that relates …acts of obligation to acts of assertion via a notion of causal implication. As our main result we show that the logic is sound and complete with respect to a class of algebraic, Kripke, and categorical models. Show more

Keywords: Speech act theory, proof theory, provability semantics, categorical logic and type theory

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 443-470, 2008

Authors: Saha, Sriparna | Bandyopadhyay, Sanghamitra

Article Type: Research Article

Abstract: The problem of classifying an image into different homogeneous regions is viewed as the task of clustering the pixels in the intensity space. In particular, satellite images contain landcover types some of which cover significantly large areas, while some (e.g., bridges and roads) occupy relatively much smaller regions. Automatically detecting regions or clusters of such widely varying sizes presents a challenging task. In this paper, a newly developed real-coded variable string length genetic fuzzy clustering technique …with a new point symmetry distance is used for this purpose. The proposed algorithm is capable of automatically determining the number of segments present in an image. Here assignment of pixels to different clusters is done based on the point symmetry based distance rather than the Euclidean distance. The cluster centers are encoded in the chromosomes, and a newly developed fuzzy point symmetry distance based cluster validity index, FSym-index, is used as a measure of the validity of the corresponding partition. This validity index is able to correctly indicate presence of clusters of different sizes and shapes as long as they are internally symmetrical. The space and time complexities of the proposed algorithm are also derived. The effectiveness of the proposed technique is first demonstrated in identifying two small objects from a large background from an artificially generated image and then in identifying different landcover regions in remote sensing imagery. Results are compared with those obtained using the well known fuzzy C-means algorithm both qualitatively and quantitatively. Show more

Keywords: Cluster validity index, fuzzy clustering, symmetry, point symmetry based distance, Kd tree, variable string length genetic algorithm, remote sensing imagery

Citation: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 471-492, 2008