Fundamenta Informaticae - Volume 63, issue 1

Authors: Fredriksson, Kimmo | Tarhio, Jorma

Article Type: Research Article

Abstract: We present an efficient algorithm for scanning Huffman compressed texts. The algorithm parses the compressed text in O(n{[log2 σ]/b}) time, where n is the size of the compressed text in bytes, σ is the size of the alphabet, and b is a user specified parameter. The method uses a variable size super-alphabet, with an average size of O({b/[H log2 σ]}) characters, where H is the entropy of the text. Each super-character is processed in O(1) time. …The algorithm uses O(2b ) space and O(b2b ) preprocessing time. The method can be easily augmented by auxiliary functions, which can e.g. decompress the text or perform pattern matching in the compressed text. We give three example functions: decoding the text in average time O(n{[log2 σ]/[Hw]}), where w is the number of bits in a machine word; an Aho-Corasick dictionary matching algorithm, which works in time O(n{[log2 σ]/b}+t), where t is the number of occurrences reported; and a shift-or string matching algorithm that works in time O(n{[log2 σ]/b}⌈(m+s-1)/w⌉+t), where m is the length of the pattern and s depends on the encoding. The Aho-Corasick algorithm uses an automaton with variable length moves, i.e. it processes variable number of states at each step. The shift-or algorithm makes variable length shifts, effectively also processing variable number of states at each step. The number of states processed in O(1) time is O(b/[H log2 σ]). The method can be applied to several other algorithms as well. Finally, we apply the methods to natural language taking the words (vocabulary) as the alphabet. This improves the compression ratio and allows more complex search problems to be solved efficiently. We conclude with some experimental results. Show more

Keywords: Huffman compression, string matching, natural language

Citation: Fundamenta Informaticae, vol. 63, no. 1, pp. 1-16, 2004

Authors: Holzer, Richard

Article Type: Research Article

Abstract: Formal contexts with unknown entries can be represented by three-valued contexts K=(G, M, {×, o, ?}, I), where a question mark indicates that it is not known whether the object g∈G has the attribute m∈M. To describe logical formulas between columns of such incomplete contexts the Kripke-semantics are used for propositional formulas over the set M of attributes. Attribute implications are considered as special propositional formulas. If a context is too large to be fully represented, …an interactive computer algorithm may help the user to get maximal information (with respect to his knowledge) about the valid attribute implications of the unknown context. This computer algorithm is called "attribute exploration". Show more

Keywords: formal concept analysis, incomplete knowledge, attribute exploration

Citation: Fundamenta Informaticae, vol. 63, no. 1, pp. 17-39, 2004

Authors: Holzer, Richard

Article Type: Research Article

Abstract: Attribute exploration is an interactive computer algorithm which helps the expert to get informations about the attribute implications of a formal context. In the part I of this paper (see [H04]) an algorithm for attribute exploration with incomplete knowledge was presented. In this part we prove the main results of the algorithm: At the end of the attribute exploration the expert gets maximal information with respect to his knowledge about the unknown universe: He gets a …list of implications which are certainly valid, a list of implications which are possibly valid, a list of counterexamples against the implications which are certainly not valid and a list of fictitious counterexamples against the implications which he answered by "unknown". He only has to check the implications which he answered by "unknown" and if he can decide for each of these implications whether it is valid or not, he gets complete knowledge about the implications of the context. Show more

Keywords: formal concept analysis, incomplete knowledge, attribute exploration

Citation: Fundamenta Informaticae, vol. 63, no. 1, pp. 41-63, 2004

Authors: Woźna, Bożena

Article Type: Research Article

Abstract: The main contribution of the paper consists in showing that the bounded model checking (BMC) method is feasible for ACTLS* (the universal fragment of CTLS*) which subsumes both ACTL and LTL. The extension to ACTLS^* is obtained by redefining the function returning the sufficient number of executions over which an ACTLS* formula is checked, and then combining the two known translations to SAT for ACTL and LTL formulas. The proposed translation of ACTLS* formulas is essentially …different from the existing translations of both ACTL and LTL formulas. Moreover, the formal treatment is the basis for the implementation of the technique in the symbolic model checker √erics. Show more

Keywords: bounded model checking, bounded semantics, logic ACTLS* (ECTLS*), bounded semantics, translation to SAT

Citation: Fundamenta Informaticae, vol. 63, no. 1, pp. 65-87, 2004

Authors: Wu, Hsien-Chu | Chang, Chin-Chen

Article Type: Research Article

Abstract: This paper proposes an effective digital watermarking scheme to protect the intellectual property rights of digital images. This scheme embeds representative watermarks into images during the process of side-match vector quantization (SMVQ)@compresses and extracts the digital watermark effectively in order to determine the ownership of the image when a dispute over intellectual property rights occurs. The method proposed in this paper embeds a watermark based on the grouping of the codewords in a state codebook, and …it stresses the fact that the SMVQ compressed image and the decompressed image both contain watermarks. In addition, the decompressed image has strong resistance against being damaged. Even under JPEG lossy compression, the watermark can still be restored effectively. The proposed method enables the watermark to be embedded directly into a compressed image that is much smaller than the original one. Once applied to the network, the method can save time in image transmission as well as storage space. Show more

Keywords: digital watermarking technique, side-match vector quantization, intellectual property rights

Citation: Fundamenta Informaticae, vol. 63, no. 1, pp. 89-106, 2004