Fundamenta Informaticae - Volume 68, issue 3

Authors: Chang, Chin-Chen | Chan, Chi-Shiang

Article Type: Research Article

Abstract: In this paper, we shall propose a method to invert halftone images. We shall use a modified look-up table to reconstruct gray level images from halftone images. In the modified look-up table training phase, we shall use a sliding window to get halftone patterns and their corresponding gray-level lists. The modified look-up table can be obtained by calculating the centroid of the gray-level lists. In the image reconstruction phase, we shall use the sliding window to …slide around the pixel to reconstruct so that we can get candidate gray values. The reconstructed gray value can be obtained by calculating the centroid of the candidate gray values. Experimental results have shown that our method indeed can get satisfied results. Show more

Keywords: Halftone image, error diffusion and look-up table

Citation: Fundamenta Informaticae, vol. 68, no. 3, pp. 207-220, 2005

Authors: Palka, Ewa

Article Type: Research Article

Abstract: The finite model property of the equational fragment of the theory of Kleene algebras is a consequence of Kozen's [3] completeness theorem. We show that, conversely, this completeness theorem can be proved assuming the finite model property of this fragment.

Keywords: Kleene algebras, action algebras, regular expressions, finite model property

Citation: Fundamenta Informaticae, vol. 68, no. 3, pp. 221-230, 2005

Authors: Stay, Michael

Article Type: Research Article

Abstract: In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are algorithmically random–there is no reason the bits should be the way they are, if we define "reason" to be a computable explanation smaller than the data itself. Since that time, only two explicit universal Chaitin machines have been proposed, both by Chaitin himself. Concrete algorithmic …information theory involves the study of particular universal Turing machines, about which one can state theorems with specific numerical bounds, rather than include terms like O(1). We present several new tiny Chaitin machines (those with a prefix-free domain) suitable for the study of concrete algorithmic information theory. One of the machines, which we call Keraia, is a binary encoding of lambda calculus based on a curried lambda operator. Source code is included in the appendices. We also give an algorithm for restricting the domain of blank-endmarker machines to a prefix-free domain over an alphabet that does not include the endmarker; this allows one to take many universal Turing machines and construct universal Chaitin machines from them. Show more

Citation: Fundamenta Informaticae, vol. 68, no. 3, pp. 231-247, 2005

Authors: Stehr, Mark-Oliver

Article Type: Research Article

Abstract: The open calculus of constructions integrates key features of Martin-Löf's type theory, the calculus of constructions, membership equational logic, and rewriting logic into a single uniform language. The two key ingredients are dependent function types and conditional rewriting modulo equational theories. We explore the open calculus of constructions as a uniform framework for programming, specification and interactive verification in an equational higher-order style. By having equational logic and rewriting logic as executable …sublogics we preserve the advantages of a first-order semantic and logical framework and we provide a foundation for a broad spectrum of applications ranging from what could be called executable mathematics, involving symbolic computations and logical proofs, to software and system engineering applications, involving symbolic execution and analysis of nondeterministic and concurrent systems. Show more

Keywords: Equational Specification, Rewriting Logic, Type Theory

Citation: Fundamenta Informaticae, vol. 68, no. 3, pp. 249-288, 2005

Authors: Wang, Guoyin Y. | Zhao, Jun | An, Jiujiang | Wu, Yu

Article Type: Research Article

Abstract: Attribute reduction is an important issue in rough set theory and has already been studied from the algebra viewpoint and information viewpoint of rough set theory respectively. However, the concepts of attribute reduction based on these two different viewpoints are not equivalent to each other. In this paper, we make a comparative study on the quantitative relationship between some basic concepts of rough set theory like attribute reduction, attribute significance and core defined from these two …viewpoints. The results show that the relationship between these conceptions from the two viewpoints is rather an inclusion than an equivalence due to the fact that the rough set theory discussed from the information point of view restricts attributes and decision tables more specifically than it does when considered from the algebra point of view. The identity of the two viewpoints will hold in consistent information decision tables only. That is, the algebra viewpoint and information viewpoint are equivalent for a consistent decision table, while different for an inconsistent decision table. The results are significant for the design and development of methods for information reduction. Show more

Keywords: Rough set, algebra viewpoint, information viewpoint, attribute reduction, attribute significance, core

Citation: Fundamenta Informaticae, vol. 68, no. 3, pp. 289-301, 2005