Fundamenta Informaticae - Volume 153, issue 4

Authors: Chiaselotti, Giampiero | Ciucci, Davide | Gentile, Tommaso | Infusino, Federico

Article Type: Research Article

Abstract: In this paper we apply rough set theory to information tables induced from finite directed graphs without loops and multiples arcs (digraphs). Specifically, we use the adjacency matrix of a digraph as a particular type of information table. In this way, we are able to explore on digraphs the notions of indiscernibility partitions, lower and upper approximations, generalized core, reducts and discernibility matrix. All these ideas will be exemplified on standard digraph families as well on examples from social networks and patterns of flight routes between airports.

Keywords: Rough set theory, digraph, attribute dependency, hypergraph minimal transversal

DOI: 10.3233/FI-2017-1542

Citation: Fundamenta Informaticae, vol. 153, no. 4, pp. 291-325, 2017

Authors: Kheirfam, Behrouz | Mohamadi-Sangachin, Mohaddeseh

Article Type: Research Article

Abstract: In this paper, we present a new second-order predictor-corrector interior-point method for semidefinite optimization. The algorithm is based on the wide neighborhood of the central path and modified corrector directions. In the corrector step, we derive the step size and corrector directions which guarantee that new iterate lies in the wide neighborhood. The iteration complexity bound is O ( n log X o • S o ɛ ) for the Nesterov-Todd direction, which coincides with the best known complexity results for semidefinite optimization. Some numerical results are provided as well.

Keywords: Semidefinite optimization, predictor-corrector interior-point method, wide neighborhood, second-order methods, iteration complexity bound

DOI: 10.3233/FI-2017-1543

Citation: Fundamenta Informaticae, vol. 153, no. 4, pp. 327-346, 2017

Authors: van Leeuwen, Jan | Wiedermann, Jiří

Article Type: Research Article

Abstract: We resolve an old problem, namely to design a ‘natural’ machine model for accepting the complements of recursively enumerable languages. The model we present is based on non-deterministic Turing machines with ‘one-sided’ advice. We prove that these machines precisely accept the co-RE languages, without restriction on the advice functions that are used. We show that for accepting a co-RE language, one-sided advice is as powerful as arbitrary advice, but also that linearly bounded one-sided advice is sufficient. However, ‘long’ sublinear advice can make Turing machines with one-sided advice accept more co-RE languages than ‘short’ sublinear advice. We prove that infinite …proper hierarchies of language classes inside co-RE can be devised, using suitable increasing sequences of bounding functions for the allowed advice. The machine model and the results dualize for the family of recursively enumerable languages. Show more

Keywords: advice functions, co-RE languages, machine models, Turing machines

DOI: 10.3233/FI-2017-1544

Citation: Fundamenta Informaticae, vol. 153, no. 4, pp. 347-366, 2017

Authors: Makuracki, Bartosz | Simson, Daniel | Zyglarski, Błażej

Article Type: Research Article

Abstract: We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix G ∨ Δ ∈ 𝕄 n ( ℤ ) defining Δ, its symmetric Gram matrix G Δ : = 1 2 [ G Δ ∨ + G Δ t r ∨ ] ∈ 𝕄 n ( …1 2 ℤ ) , and the Gram quadratic form q Δ : ℤn → ℤ. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix G Δ ∈ 𝕄n (ℤ) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram ℤ-congruence Δ ~ℤ Δ′, where Δ ~ℤ Δ′ means that G Δ ′ = Btr · G Δ · B , for some B ∈ 𝕄n (ℤ) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph 𝒟n ∨ {ℬn , 𝒞n , ℱ4 , 𝒢2 } with loops and a suitably chosen sequence t • − of the inflation operators of one of the types Δ ′ ↦ t a − Δ ′ and Δ ′ ↦ t a b − Δ ′ such that the composite operator Δ ↦ t • − Δ reduces Δ to the bigraph 𝒟n such that Δ ~ℤ 𝒟n and the bigraphs Δ, 𝒟n have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∈ 𝕄n (ℤ), with det B = ±1, defining the weak Gram ℤ-congruence Δ ~ℤ 𝒟n , that is, satisfying the equation G 𝒟n = Btr · G Δ · B . Show more

Keywords: edge-bipartite graph, Dynkin graph, inflation algorithm, Gram matrix, unit quadratic form, Coxeter spectrum, isotropy group

DOI: 10.3233/FI-2017-1545

Citation: Fundamenta Informaticae, vol. 153, no. 4, pp. 367-398, 2017

Authors: Wroński, Michał | Dryło, Robert | Kijko, Tomasz | Bora, Piotr

Article Type: Research Article

Abstract: The GLV method allows to improve scalar multiplication on an elliptic curve E /𝔽q with an efficiently computable endomorphism Φ : E → E over 𝔽q . For points in a subgroup of large prime order r this requires decomposition of scalar k = k 0 + k 1 λ mod r , where Φ acts on the subgroup of order r as multiplication by λ ∈ 𝔽r and k 0 , k 1 are integers O ( r ) . In …this note we consider the case when λ is of the form λ = 2s + a , where a is a small integer and λ = O ( r ) , which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∈ {2s , 2s − 1} and various security levels. Show more

Keywords: Elliptic curves, scalar multiplication, GLV method, CM method, efficient hardware implementation

DOI: 10.3233/FI-2017-1546

Citation: Fundamenta Informaticae, vol. 153, no. 4, pp. 399-413, 2017

Article Type: Other

Citation: Fundamenta Informaticae, vol. 153, no. 4, pp. 415-416, 2017