Fundamenta Informaticae - Volume 139, issue 3

Authors: Chojnacki, Szymon | Kłopotek, Mieczysław

Article Type: Research Article

Abstract: Latency of user-based and item-based recommenders is evaluated. The two algorithms can deliver high quality predictions in dynamically changing environments. However, their response time depends not only on the size, but also on the structure of underlying datasets. This constitutes a major drawback when compared to two other competitive approaches i.e. content-based and model-based systems. Therefore, we believe that there exists a need for comprehensive evaluation of the latency of the two algorithms. During a typical worst case scenario analysis of collaborative filtering algorithms two assumption are made. The first assumption says that data are stored in dense collections. …The second assumption states that large amount of computations can be performed in advance during the training phase. As a result it is advised to deploy user-based system when the number of users is relatively small. Item-based algorithms are believed to have better technical properties when the number of items is small. We consider a situation in which the two assumptions are not necessarily met. We show that even though the latency of the two methods depends heavily on the proportion of users to items, this factor does not differentiate the two methods. We evaluate the algorithms with several real-life datasets. We augment the analysis with both graph-theoretical and experimental techniques. Show more

DOI: 10.3233/FI-2015-1233

Citation: Fundamenta Informaticae, vol. 139, no. 3, pp. 229-248, 2015

Authors: Kasjan, Stanisław | Simson, Daniel

Article Type: Research Article

Abstract: This paper can be viewed as a third part of our paper [Fund. Inform. 2015, in press]. Following our Coxeter spectral study in [Fund. Inform. 123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category 𝒰 ℬ i g r n of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study a larger category ℛ ℬ i g r n of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual ℤ-congruences ~Z and ≈Z . The positive graphs Δ in ℛ ℬ …i g r n , with dotted loops, are studied by means of the complex Coxeter spectrum s p e c c Δ   ⊂ ℂ , the irreducible mesh root systems of Dynkin types 𝔹 n ,   n ≥ 2 , ℂ n ,   n ≥ 3 ,   𝔽 4 ,   𝔾 2 , the isotropy group Gl(n , ℤ)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] Here we present combinatorial algorithms for constructing the isotropy groups G1 ( n ,   ℤ ) Δ . One of the aims of our three paper series is to develop computational tools for the study of the ℤ-congruence ~ℤ and the following Coxeter spectral analysis question: “Does the congruence Δ ≈ℤ Δ′ holds, for any pair of connected positive graphs Δ ,   Δ ′ ∈ ℛ ℬ i g r n such that spec c Δ = spec c Δ ′ and the numbers of loops in Δ and Δ′ coincide? ” For this purpose, we construct in this paper a extended inflation algorithm Δ ↦ 𝒟 Δ , with 𝒟 Δ ∼ ℤ Δ , that allows a reduction of the question to the Coxeter spectral study of the G1 ( n ,   ℤ ) D -orbits in the set M o r D   ⊂   𝕄 n ( ℤ ) of matrix morsifications of the associated edge-bipartite Dynkin graph D = 𝒟 Δ ∈ ℛ B i g r n . We also outline a construction of a numeric algorithm for computing the isotropy group G1 ( n ,   ℤ ) Δ of any connected positive edge-bipartite graph Δ in ℛ ℬ i g r n . Finally, we compute the finite isotropy group G1 ( n ,   ℤ ) D , for each of the Cox-regular edge-bipartite Dynkin graphs D. Show more

Keywords: poset, Coxeter spectrum, Dynkin diagram, Coxeter-Dynkin type, isotropy group

DOI: 10.3233/FI-2015-1234

Citation: Fundamenta Informaticae, vol. 139, no. 3, pp. 249-275, 2015

Authors: Mogavero, Fabio | Murano, Aniello | Sorrentino, Loredana

Article Type: Research Article

Abstract: Parity games are infinite-duration two-player turn-based games that provide powerful formal-method techniques for the automatic synthesis and verification of distributed and reactive systems. This kind of game emerges as a natural evaluation technique for the solution of the μ -calculus model-checking problem and is closely related to alternating ω -automata. Due to these strict connections, parity games are a well-established environment to describe liveness properties such as “every request that occurs infinitely often is eventually responded”. Unfortunately, the classical form of such a condition suffers from the strong drawback that there is no bound on the effective time …that separates a request from its response, i.e., responses are not promptly provided. Recently, to overcome this limitation, several variants of parity game have been proposed, in which quantitative requirements are added to the classic qualitative ones. In this paper, we make a general study of the concept of promptness in parity games that allows to put under a unique theoretical framework several of the cited variants along with new ones. Also, we describe simple polynomial reductions from all these conditions to either Büchi or parity games, which simplify all previous known procedures. In particular, they allow to lower the complexity class of cost and bounded-cost parity games recently introduced. Indeed, we provide solution algorithms showing that determining the winner of these games is in UPTIME ∩ COUPTIME . Show more

Keywords: Parity games, formal verification, liveness, promptness, cost-parity games, quantitative games, UPTIME ∩ COUPTIME

DOI: 10.3233/FI-2015-1235

Citation: Fundamenta Informaticae, vol. 139, no. 3, pp. 277-305, 2015

Authors: Shakiba, Ali | Hooshmandasl, Mohammad R.

Article Type: Research Article

Abstract: In this paper, we investigate properties of the lower and upper approximations of an S-approximation space under different assumptions for its S operator. These assumptions are partial monotonicity, complement compatibility and functional partial monotonicity. We also extend the theory of three way decisions to non-inclusion relations. Also in this work, a new representation for partial monotone S-approximation spaces, called inflections, is introduced. We will also discuss the computational complexity of representing an S-approximation space in terms of inflection sets. Finally, the usefulness of the introduced concepts is illustrated by an example.

Keywords: S-approximation Spaces, Three-way Decisions, Partial Monotone, Complement Compatibility, Rough Set Theory, Rough Mereology

DOI: 10.3233/FI-2015-1236

Citation: Fundamenta Informaticae, vol. 139, no. 3, pp. 307-328, 2015