Fundamenta Informaticae - Volume 89, issue 2-3

Authors: Cheng, Chien-Fu | Wang, Shu-Ching | Liang, Tyne

Article Type: Research Article

Abstract: Since wireless communication and mobile computing are becomingmore and more ubiquitous, the reliability and fault tolerance of the Mobile Ad-hoc Network (MANET) has become an important topic. In order to provide a reliable environment, a mechanism that allows a set of nodes to reach a common agreement, even in the presence of faulty nodes, is needed. Therefore, the Byzantine Agreement (BA) problem has drawn attention of more researchers. Traditionally, the BA problem was focused on wired …networks. We know that the physical topology of a wired network is static, but the physical topology of an MANET is dynamic. Thus, previous BA protocols are not applicable in an MANET. In this paper, a new protocol is proposed to solve the BA problem with malicious faulty components in dynamic MANET. Furthermore, we also propose a new Fault Diagnosis Agreement (FDA) protocol to detect/locate faulty components to provide a highly reliable environment. From the performance perspective, the proposed protocols use the minimum number of message exchanges and can tolerate/detect/locate the maximum number of faulty nodes allowed in the dynamic network. Show more

Keywords: Byzantine agreement, fault diagnosis agreement, malicious, mobile ad-hoc network

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 161-187, 2008

Authors: Dembczyński, Krzysztof | Kotłowski, Wojciech | Sydow, Marcin

Article Type: Research Article

Abstract: The paper concerns the problem of predicting behaviour of web users, based on real historical data which constitutes an important issue in web mining. The research reported here was conducted while the authors participated in the international ECML/ PKDD 2007 Discovery Challenge competition – Track 1. The results presented here ended up as the winning solution to the contest. We describe the contest tasks and the real industrial datasets concerning …the recorded behaviour of sample of Polish Web users on which our experiments were performed. We present the whole extensive experimental process from the data preprocessing phase to exploratory analysis of the data to the experimental comparison and discussion of various prediction models which we examined. As we explain, our solution has low time and space complexity, scales well with large datasets and, at the same time, produces high-quality results. Show more

Keywords: user behaviour prediction, web mining, machine learning, experimentation, data analysis

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 189-206, 2008

Authors: Fülöp, Zoltán | Muzamel, Loránd

Article Type: Research Article

Abstract: We consider pebble macro tree transducers with call-by-name semantics and strong pebble handling. The latter means that the last dropped pebble can be lifted regardless of the position of the reading head. This tree transducer concept is a generalization of the pebblemacro tree transducer introduced by J. Engelfriet and S. Maneth in 2003, however we leave the original name untouched. Our main results are that (1) every n-pebble macro tree transformation can be characterized by …the composition of an n-pebble tree transformation and a yield tree transformation, and (2) each n-pebble tree transformation can also be computed by an (n − 1)-pebble macro tree transformation. Using (1) and (2) we prove that every n-pebblemacro tree transformation appears as the composition of n+2 stay-macro tree transformations and hence, the inverses of n-pebble macro tree transformations preserve regularity. Finally, using the previous results, we show that the type checking problem for n-pebble macro tree transducers is decidable. Show more

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 207-257, 2008

Authors: Grahne, Gösta | Thomo, Alex | Wadge, William W.

Article Type: Research Article

Abstract: In this paper, we introduce preferential regular path queries. These are regular path queries whose symbols are annotated with preference weights for "scaling" up or down the intrinsic importance of matching a symbol against a (semistructured) database edge label. Annotated regular path queries are expressed syntactically as annotated regular expressions. We interpret these expressions in a uniform semiring framework, which allows different semantic interpretations for the same syntactic annotations. For our preference …queries, we study three important aspects: (1) (progressive) query answering (2) (certain) query answering in LAV data-integration systems, and (3) query containment and equivalence. In all of these, we obtain important positive results, which encourage the use of our preference framework for enhanced querying of semistructured databases. Show more

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 259-288, 2008

Authors: Jurdziński, Tomasz

Article Type: Research Article

Abstract: The set of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Moreover, growing context-sensitive languages and their deterministic counterpart called Church-Rosser Languages (CRL) complement the Chomsky hierarchy in a natural way [13]. In this paper, closures of GCSL under the boolean operations are investigated. It is shown that there exists an infinite intersection hierarchy for GCSL and CRL, answering an open problem …from [2]. Furthermore, the expressive power of the boolean closures of GCSL, CRL, CFL and LOGCFL are compared. Show more

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 289-305, 2008

Authors: Leivant, Daniel

Article Type: Research Article

Abstract: Referring to symbolic computing permits extremely simple proofs of undecidability for first-order logic and theories of basic structures. Using grammars we obtain a trivial proof that firstorder validity is undecidable (already for formulas with quantifier prefix ∃∃ and referring to only one unary relation and one binary function [2]). A similar proof yields Gödel's First Incompleteness Theorem for the structure of strings; undecidability for arithmetic follows by noting that addition and multiplication …permit direct coding of string concatenation. Show more

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 307-312, 2008

Authors: Nepomniaschaya, Anna

Article Type: Research Article

Abstract: We propose a simple data structure for an efficient implementation of the Italiano algorithms for the dynamic updating of the transitive closure of a directed graph represented as adjacency matrix on a model of associative (or content addressable) parallel processors with vertical processing (the STAR–machine). Associative versions of the Italiano algorithms are represented as procedures DeleteArc1 and InsertArc1. We prove the correctness of these procedures and evaluate their time and space complexity. We also …present the main advantages of associative versions of the Italiano algorithms. Show more

Keywords: Directed graph, spanning tree, adjacency matrix, transitive closure of a directed graph, incremental algorithm, decremental algorithm, associative parallel processor, access data by contents

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 313-329, 2008

Authors: Saha, Indranil | Bhattacharya, Bhargab B. | Zhang, Sheng | Seth, Sharad C.

Article Type: Research Article

Abstract: Double-tree-scan (DTS) is a new scan-path architecture that is deemed to be suitable for low-power testing of VLSI circuits. A full DTS resembles two complete k-level (k > 0) binary trees whose leaf nodes are merged pair-wise, and thus consists of exactly N_{k} = 3 × 2^{k} − 2 nodes. In this paper, the problem of planar straight-line embedding of a "double-tree graph" on a rectangular grid is investigated and an O(N_{k} …) time algorithm for drawing it, is described. The embedding requires at most 2N_{k} grid points, with an aspect ratio lying between 1 and �. Next, techniques of embedding a partial DTS is considered when the number of nodes n ≠ 3 × 2^{k} − 2, for some k. Layouts of double-tree scan-paths for some benchmark circuits are also presented to demonstrate the results. Show more

Keywords: DTS architecture, graph drawing, planar straight-line embedding

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 331-344, 2008

Authors: Švrček, Filip

Article Type: Research Article

Abstract: SBL¬-algebras were introduced as algebraic models for the basic strict fuzzy logic SBL extended with an involutive negation. The open problemof a minimal independent axiomatic system of the SBL¬-algebras is resolved in the paper.

Keywords: t-norm, involutive residuated lattice, SBL-algebra

Citation: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 345-368, 2008