Fundamenta Informaticae - Volume 62, issue 3-4

Authors: Chang, Chin-Chen | Tsai, Piyu | Lin, Min-Hui

Article Type: Research Article

Abstract: In this paper, a new palette-based image steganography is proposed. Palette-based images such as GIF files have been widely used on the Internet and web pages such that all browsers can recognize them. Palette-based images can be used as good carriers for transmitting secret messages. In this scheme, the Least Significant Bits (LSBs) of the palette-based image are utilized in order to hide the secret message by using the computational information hiding technique. The adaptive hiding …capacity can be computed according to different sizes of the embedding block. Experimental results also show that existing artifacts in the traditional LSB-based method are unnoticeable. The number of modification pixels in the embedding process is decreased, while good stego-image quality is maintained, and the cover image is left unblemished by camouflaged information. Furthermore, the feature of adaptive hiding capacity provides the possibility of protecting different sizes of embedded secret messages. Show more

Keywords: information hiding, palette-based image, steganography

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 275-289, 2004

Authors: Cassez, Franck | Pagetti, Claire | Roux, Olivier

Article Type: Research Article

Abstract: In this paper we present a timed extension of the ALTARICA formalism. Following previous works, we first extend the semantics of ALTARICA with time and define timed components and timed nodes. Moreover we lift the priority features of ALTARICA to the timed case. We obtain a timed version of ALTARICA, called ALTARICA. Finally we give a translation of a ALTARICA specification into a usual timed automaton. These are the semantic foundations of a high-level hierarchical language …for the specification of timed systems. Show more

Keywords: ALTARICA, semantics, timed automata

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 291-332, 2004

Authors: Finkel, Olivier

Article Type: Research Article

Abstract: ω-powers of finitary languages are ω-languages in the form Vω , where V is a finitary language over a finite alphabet Sigma. Since the set Σω of infinite words over Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers naturally arises and has been raised by Niwinski [13], by Simonnet [15], and by Staiger [18]. It has been proved in [14] that for each integer n≥1, there …exist some ω-powers of context free languages which are Πn 0 -complete Borel sets, and in [5] that there exists a context free language L such that Lω is analytic but not Borel. But the question was still open whether there exists a finitary language V such that Vω is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank. Show more

Keywords: infinite words, ω-languages, ω-powers, Cantor topology, topological complexity, Borel sets, infinite rank

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 333-342, 2004

Authors: Johnson, Chris A.

Article Type: Research Article

Abstract: A top-down method is presented for compiling queries in unstratified propositional disjunctive deductive databases under the disjunctive well-founded semantics. Compilation entails the construction of a set of compilation trees, and the run-time processing of the compiled query then amounts to checking that some such tree can be extended within the extensional database to yield a tree that encapsulates a proof of the original query. Issues surrounding the extension of our techniques to the first order level …are discussed. Show more

Keywords: disjunctive deductive databases, disjunctive well-founded semantics, query compilation, top-down computation

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 343-368, 2004

Authors: Karpinski, Marek | Kowaluk, Miroslaw | Lingas, Andrzej

Article Type: Research Article

Abstract: The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3≤k≤8, by deriving some improved transformations from a maximum cut into a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and …in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively. Show more

Keywords: graph bisection, approximation algorithms, regular graphs

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 369-375, 2004

Authors: Liberatore, Paolo | Schaerf, Marco

Article Type: Research Article

Abstract: A propositional knowledge base can be seen as a compact representation of a set of models. When a knowledge base T is updated with a formula P, the resulting set of models can be represented in two ways: either by a theory T' that is equivalent to T*P or by the pair 〈T,P〉. The second representation can be super-polinomially more compact than the first. In this paper, we prove that the compactness of this representation depends on the specific semantics …of *, e.g., Winslett's semantics is more compact than Ginsberg's. Show more

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 377-393, 2004

Authors: Marciniec, Jacek

Article Type: Research Article

Abstract: In this paper we focus on the properties of infinite sets of types that have finite substitutional images. Since the number of such images may be infinite, we provide the way of its reduction. Having this done, we apply the new methods in the field of learnability of classical categorial grammars.

Keywords: unification, learning, categorial grammar

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 395-407, 2004

Authors: De, Supriya Kumar

Article Type: Research Article

Abstract: In this paper, cluster analysis based on fuzzy relations is investigated. This paper starts with fuzzy proximity relations and cluster analysis based on fuzzy proximity relation is performed by using rough approximation. A clustering algorithm has been proposed and explained with an example.

Keywords: cluster analysis, fuzzy sets, fuzzy proximity relations, rough set

Citation: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 409-417, 2004