Fundamenta Informaticae - Volume 128, issue 4

Authors: Bergstra, J.A. | Middelburg, C.A.

Article Type: Research Article

Abstract: We introduce an algebra of data linkages. Data linkages are intended for modelling the states of computations in which dynamic data structures are involved. We present a simple model of computation in which states of computations are modelled as data linkages and state changes take place by means of certain actions. We describe the state changes and replies that result from performing those actions by means of a term rewriting system with rule priorities. The model in question is an upgrade of molecular dynamics. The upgrading is mainly concerned with the features to deal with values and the features to …reclaim garbage. Show more

Keywords: data linkage algebra, data linkage dynamics, garbage collection, priority rewrite system

DOI: 10.3233/FI-2013-950

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 367-412, 2013

Authors: Ferilli, Stefano | Esposito, Floriana

Article Type: Research Article

Abstract: Standardized processes are important for correctly carrying out activities in an organization. Often the procedures they describe are already in operation, and the need is to understand and formalize them in a model that can support their analysis, replication and enforcement. Manually building these models is complex, costly and error-prone. Hence, the interest in automatically learning them from examples of actual procedures. Desirable options are incrementality in learning and adapting the models, and the ability to express triggers and conditions on the tasks that make up the workflow. This paper proposes a framework based on First-Order Logic that solves many …shortcomings of previous approaches to this problem in the literature, allowing to deal with complex domains in a powerful and flexible way. Indeed, First-Order Logic provides a single, comprehensive and expressive representation and manipulation environment for supporting all of the above requirements. A purposely devised experimental evaluation confirms the effectiveness and efficiency of the proposed solution. Show more

Keywords: Workflow, Process Models, First Order Logic, Relational Learning

DOI: 10.3233/FI-2013-951

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 413-443, 2013

Authors: Han, Yo-Sub

Article Type: Research Article

Abstract: State elimination is an intuitive and easy-to-implement algorithm that computes a regular expression from a finite-state automaton (FA). It is very hard to compute the shortest regular expression for a given FA in general and we cannot avoid the exponential blow-up. This implies that state elimination cannot avoid the exponential blow-up either. Nevertheless, since the size of a regular expression by state elimination depends on the state removal sequence, we can have a shorter regular expression if we choose a better removal sequence for state elimination. This observation motivates us to examine state elimination heuristics based on the structural properties …of the input FA and implement state elimination using the heuristics that run in polynomial time. We demonstrate the effectiveness of our algorithm by experiment results. Show more

Keywords: finite-state automata, regular expressions, state elimination, heuristics

DOI: 10.3233/FI-2013-952

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 445-462, 2013

Authors: Krasiński, Tadeusz | Sakowski, Sebastian | Waldmajer, Jacek | Popławski, Tomasz

Article Type: Research Article

Abstract: In the paper we present a theoretical analysis of extension of the finite automaton built on DNA (introduced by the Shapiro team) to an arbitrary number of states and symbols. In the implementation we use a new idea of several restriction enzymes instead of one. We give arithmetical conditions for the existence of such extensions in terms of ingredients used in the implementation.

Keywords: Biomolecular computer, DNA automaton, DNA computing

DOI: 10.3233/FI-2013-953

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 463-474, 2013

Authors: Wang, Xiangyang | Yang, Hongying | Wang, Jing | Chen, Lili | Niu, Panpan

Article Type: Research Article

Abstract: Robust digital watermarking has been an active research topic in the last decade. As one of the promising approaches, feature point based image watermarking has attracted many researchers. However, the related work usually suffers from the following limitations: 1) The feature point detector is sensitive to texture region, and some noise feature points are always detected in the texture region. 2) The feature points focus too much on high contrast region, and the feature points are distributed unevenly. Based on Bayesian image segmentation, we propose a local geometrically invariant image watermarking scheme with good visual quality in this paper. Firstly, …the Bayesian image segmentation is used to segment the host image into several homogeneous regions. Secondly, for each homogeneous region, image feature points are extracted using the multiscale Harris-Laplace detector, and the corresponding invariant local image regions are constructed adaptively. Finally, by taking the human visual system (HVS) into account, digital watermark is repeatedly embedded into local image regions by modulating the magnitudes of DFT coefficients. By binding the digital watermark with the invariant local image regions, the watermark detection can be done without synchronization error. Experimental results show that the proposed image watermarking is not only invisible and robust against common image processing operations such as sharpening, noise adding, and JPEG compression etc, but also robust against the geometric distortions. Show more

Keywords: Image watermarking, geometric distortion, Bayesian image segmentation, local image region, human visual system

DOI: 10.3233/FI-2013-954

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 475-501, 2013

Authors: Wang, Zhaohao | Shu, Lan | Ding, Xiuyong

Article Type: Research Article

Abstract: Rough set theory is an important technique in knowledge discovery in databases. In covering-based rough sets, seven types of rough set models were established in recent years. This paper defines the concept of maximal description of an element, and further explores the properties and structures of several types by means of the concepts of maximal description and minimal description. Finally, we study the relationship between covering-based rough sets and the generalized rough sets based on binary relation.

Keywords: Rough sets, Granular computing, Generalized rough sets, Coverings, Maximal descriptions, Data mining

DOI: 10.3233/FI-2013-955

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 503-526, 2013

Article Type: Other

Citation: Fundamenta Informaticae, vol. 128, no. 4, pp. 527-528, 2013