Fundamenta Informaticae - Volume 86, issue 1-2

Authors: Bijak, Katarzyna

Article Type: Research Article

Abstract: In this paper genetic algorithms are used in estimation and decoding processes of a Hidden Markov Model (HMM) and a hybrid HMM/ANN model with conditional binomial distributions. The hybrid model combines a hidden Markov chain with a perceptron which is assumed to constitute a match network. Genetic algorithms are applied here instead of the traditional methods such as the EM algorithm and the Viterbi algorithm. The paper demonstrates performance of an HMM and a hybrid model …in modeling the annual number of months, in which some seismic events are recorded. Parameters of the discrete-time two-state models are estimated using the maximum likelihood method, on the basis of data on seismic events that were recorded in Romania in years 1901¨C1990. Then, on the basis of the estimation results, the most likely sequences of states of the hidden Markov chains are found. Show more

Keywords: HiddenMarkovModels, hybrid HMM/ANN models, Markov chains, neural networks, genetic algorithms, seismic events

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 1-17, 2008

Authors: Bloom, Stephen L. | Ésik, Zoltan | Kuich, Werner

Article Type: Research Article

Abstract: A Conway semiring is a semiring S equipped with a unary operation *: S → S, always called 'star', satisfying the sum star and product star identities. It is known that these identities imply a Kleene type theorem. Some computationally important semirings, such as N or N^{rat} ≪Σ≫ of rational power series of words on Σ with coefficients in N, cannot have a total star operation satisfying the Conway identities. We introduce here partial Conway …semirings, which are semirings S which have a star operation defined only on an ideal of S; when the arguments are appropriate, the operation satisfies the above identities. We develop the general theory of partial Conway semirings and prove a Kleene theorem for this generalization. Show more

Keywords: Conway semiring, iteration semiring, Kleene theorem

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 19-40, 2008

Authors: Denis, François | Esposito, Yann

Article Type: Research Article

Abstract: The goal of the present paper is to provide a study of rational stochastic languages over a semiring K ∈ {Q,R,Q^+ ,R^+ }. A rational stochastic language is a probability distribution over a free monoid Σ*, which is rational over K, that is, which can be generated by a multiplicity automaton with parameters in K. We study the relations between the classes of rational stochastic languages S^{rat} _K (Σ). …We define the notion of residual language of a stochastic language and we use it to investigate properties of several subclasses of rational stochastic languages. Then, we study the representation of rational stochastic languages by means of multiplicity automata. Lastly, we show some connections between properties of rational stochastic languages and results obtained in the field of probabilistic grammatical inference. Show more

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 41-77, 2008

Authors: Dinu, Liviu P. | Popescu, Marius

Article Type: Research Article

Abstract: The multi-criteria decision making process can be summarized as follows. Given a pattern d and a set C = {c_1 , c_2 , …, c_m } of allmpossible categories of d, we are interested in predicting its class by using a set of n classifiers l_1 , l_2 , …, l_n . Each classifier produces a ranking of categories. In this paper we propose and test a decision method which …combines the rankings by using a particular method, called rank distance categorization. This method is actually based on the rank distance, a metric which was successfully used in computational linguistics and bioinformatics. We define the method, present some of its mathematical and computational properties and we test it on the digit dataset consisting of handwritten numerals ('0', …, '9') extracted from a collection of Dutch utility maps. We compare our experimental results with other reported experiments which used the same dataset but different combining methods. Show more

Keywords: rank distance, rank aggregation problem, multi-criteria decision

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 79-91, 2008

Authors: Hamzeh, Ali | Rahmani, Adel

Article Type: Research Article

Abstract: Learning Classifier Systems are Evolutionary Learning mechanisms which combine Genetic Algorithm and the Reinforcement Learning paradigm. Learning Classifier Systems try to evolve state-action-reward mappings to propose the best action for each environmental state to maximize the achieved reward. In the first versions of learning classifier systems, state-action pairs can only be mapped to a constant real-valued reward. So to model a fairly complex environment, LCSs had to develop redundant state-action pairs which had …to be mapped to different reward values. But an extension to a well-known LCS, called Accuracy Based Learning Classifier System or XCS, was recently developed which was able to map state-action pairs to a linear reward function. This new extension, called XCSF, can develop a more compact population than the original XCS. But some further researches have shown that this new extension is not able to develop proper mappings when the input parameters are from certain intervals. As a solution to this issue, in our previous works, we proposed a novel solution inspired by the idea of using evolutionary approach to approximate the reward landscape. The first results seem promising, but our approach, called XCSFG, converged to the goal very slowly. In this paper, we propose a new extension to XCSFG which employs micro-GA which its needed population is extremely smaller than simple GA. So we expect micro-GA to help XCSFG to converge faster. Reported results show that this new extension can be assumed as an alternative approach in XCSF family with respect to its convergence speed, approximation accuracy and population compactness. Show more

Keywords: FunctionApproximation, Learning Classifier Systems, MicroGenetic Algorithm, XCSF

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 93-111, 2008

Authors: Hu, Yu-Chen | Tsou, Chih-Chiang | Su, Bing-Hwang

Article Type: Research Article

Abstract: A novel LSB-based image-hiding scheme that embeds secret data into the grayscale cover image is proposed in this paper. Several LSB-based image hiding schemes such as simple LSB substitution technique, optimal LSB substitution technique, greedy LSB substitution technique, modulus LSB substitution technique had been proposed. To provide good image quality of the stego-image while requiring a low computational cost, the greedy method and modulus function are employed in the proposed scheme. According to the results, …the proposed scheme provides better image quality of stego-image than the comparative schemes while consuming a low computational cost. Show more

Keywords: image hiding, LSB substitution technique, modulus LSB substitution technique, greedy method

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 113-126, 2008

Authors: Jonoska, Nataša | Kari, Lila | Mahalingam, Kalpana

Article Type: Research Article

Abstract: In this paper we study a generalization of the classical notions of solid codes and commafree codes: involution solid codes (�-solid) and involution join codes (�-join). These notions are motivated by DNA strand design where Watson-Crick complementarity can be formalized as an antimorphic involution. We investigate closure properties of these codes, as well as necessary conditions for �-solid codes to be maximal. We show how the concept of �-join can be utilized such that codes that …are not themselves �-comma free can be split into a union of subcodes that are �-comma free. Show more

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 127-142, 2008

Authors: Maji, Pradipta

Article Type: Research Article

Abstract: Two new operators, namely, dependency vector (DV) and derived complement vector (DCV) are introduced in this paper to characterize the attractor basins of the additive fuzzy cellular automata (FCA) based associative memory, termed as fuzzy multiple attractor cellular automata (FMACA). The introduction of DV and DCV makes the complexity of the attractor basin identification algorithm linear in time. The characterization of the FMACA using DV and DCV establishes the fact that the FMACA provides both equal …and unequal size of attractor basins. Finally, a set of algorithms is proposed to synthesize the FCA rules, attractors, and predecessors of attractors from the given DV and DCV in linear time complexity. Show more

Keywords: Cellular automata, fuzzy cellular automata, associative memory, attractor basin

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 143-168, 2008

Authors: Nadarajah, Saralees

Article Type: Research Article

Abstract: In the recent paper by Soundararajan and Sarkar (2003), the normalized cut, a graph partitioning measure for perceptual organization, was shown to be a sum of two beta distributed random variables and expressions derived for its mean and mode. Here, it is pointed out that the given expression for the mode is incorrect. The correct expression is derived and the implications of the error discussed.

Keywords: Beta distribution, Graph partitioning, Mean, Mode, Normalized cut, Sum of two random variables

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 169-173, 2008

Authors: Ramadoss, Balakrishnan | Rajkumar, Kannan

Article Type: Research Article

Abstract: Dance video is one of the important types of narrative videos with an interesting and semantics-rich content. Modeling the expressive dance semantics is a real challenging task, compared to the other types of videos such as news, sports and video streams. This paper proposes a formal conceptual model based on the theory of regular tree automata called, DanceGrammar. The DanceGrammar and its tree automaton represent the dance pieces that are associated with the accompanying song. A …dance piece incorporates many dance video semantics such as dancer objects, actors, dance movements, emotions and spatio-temporal relationships among the dancers and their actors. This paper then outlines the translation rules to convert the tree automaton of the Dance- Grammar into W3C XML Schema and presents the underlying XML Schema representations. Show more

Keywords: Actors, Dance Videos, Dance Semantics, Regular Tree Automata, XML Schema

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 175-189, 2008

Authors: Terlikowski, Tomasz

Article Type: Research Article

Abstract: We continue the analysis of the notion of information in a two-stage decision process. In the previous work and in the present one, when examining specific concepts and types of information, we achieve a better understanding of mathematical contents of the notion. Only elementary set-theoretical tools are used. All the formalism previously introduced is largely used here; it is shortly recalled here. We try to formally approach several concepts: uncertainty, measurement and prediction, often …applied in decision-making theory. Then, after introducing the notion of independent information, we attempt to formulate a precise definition of what we understand as decision making problem. Show more

Keywords: decision variant, basic form of information, informational set, uncertainty, independent information, decision making problem

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 191-212, 2008

Authors: Tzacheva, Angelina A. | Tsay, Li-Shiang

Article Type: Research Article

Abstract: A rule is actionable, if a user can do an action to his/her advantage based on that rule. Actionability can be expressed in terms of attributes that are present in a database. Action rules are constructed from certain pairs of classification rules, previously extracted from the same database, each defining a preferable decision class. It is assumed that attributes are divided into two groups: stable and flexible. Flexible attributes provide a tool for making hints to …a user to what changes within some values of flexible attributes are needed to re-classify a group of objects, supporting the action rule, from one decision class to another, more desirable, one. Changes of values of some flexible attributes can be more expensive than changes of other values. To investigate such cases, the notion of a cost is introduced and it is assigned by an expert to each such a change. Action rules construction involves both flexible and stable attributes listed in certain pairs of classification rules. The values of stable attributes are used to create action forest. We propose a new strategy which combines the action forest algorithm of extracting action rules and a heuristic strategy for generating reclassification rules of the lowest cost. This new strategy presents an enhancement to both methods. Show more

Keywords: Action Rules, Reclassification Model, Actionability

Citation: Fundamenta Informaticae, vol. 86, no. 1-2, pp. 213-225, 2008