Fundamenta Informaticae - Volume 160, issue 4

Authors: Carayol, Arnaud | Löding, Christof | Serre, Olivier

Article Type: Research Article

Abstract: We consider imperfect information stochastic games where we require the players to use pure (i.e . non randomised) strategies. We consider reachability, safety, Büchi and co-Büchi objectives, and investigate the existence of almost-sure/positively winning strategies for the first player when the second player is perfectly informed or more informed than the first player. We obtain decidability results for positive reachability and almost-sure Büchi with optimal algorithms to decide existence of a pure winning strategy and to compute one if it exists. We complete the picture by showing that positive safety is undecidable when restricting to pure strategies even if the …second player is perfectly informed. Show more

Keywords: Two-player imperfect information stochastic games, pure strategies, decidability/undecidability

DOI: 10.3233/FI-2018-1687

Citation: Fundamenta Informaticae, vol. 160, no. 4, pp. 361-384, 2018

Authors: Kong, Qingzhao | Xu, Weihua

Article Type: Research Article

Abstract: Rough set theory is one of the most important tools for data mining. The covering rough set (CRS) model is an excellent generalization of Pawlak rough sets. In this paper, we first investigate a number of basic properties of two types of CRS models. Especially, we study the operation properties of the two types of CRS models with respect to the unary covering. Meanwhile, several corresponding algorithms are constructed for computing the intersection and union of rough sets and some examples are employed to illustrate the effectiveness of these algorithms.Finally, as an application of the operation properties of CRS, some …basic algebraic properties of CRS are explored. It is evident that these results will enrich the theory of covering rough sets. Show more

Keywords: Rough sets, unary, covering, operation properties, algebraic properties

DOI: 10.3233/FI-2018-1688

Citation: Fundamenta Informaticae, vol. 160, no. 4, pp. 385-408, 2018

Authors: Ming, Yang | Wang, Yumin

Article Type: Research Article

Abstract: Proxy signature is extension of the standard signature, in which the original signer can delegate his or her signing capability to proxy signer in such a way that the latter can sign messages on behalf of the former. Certificateless cryptography eliminates the need of certificates in the traditional public key cryptography and solves the inherent key escrow problem in the identity based cryptography. In this paper, we extend security model of proxy signature to certificateless setting and formalize the security model of certificateless proxy signature. We propose a certificateless proxy signature scheme with concrete implementation which is probably secure in …the standard model. Furthermore, the proposed scheme is proven to be existentially unforgeable under the hardness of the computational Diffie-Hellman problem. Show more

Keywords: Proxy signature, Certificateless cryptography, Certificateless proxy signature, Bilinear pairings, Standard model

DOI: 10.3233/FI-2018-1689

Citation: Fundamenta Informaticae, vol. 160, no. 4, pp. 409-445, 2018

Authors: Roayaei, Mehdy | Razzazi, MohammadReza

Article Type: Research Article

Abstract: We consider an augmentation problem to establish point-to-point connectivity on unweighted graphs where there is no restriction on choosing the augmenting edges (arcs). Given a directed (an undirected) graph G and set P = {(si , ti ) : 1 ≤ i ≤ m } of pairs of vertices in the graph, one has to find the minimum cardinality set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented in order to have) directed paths between the specified pairs of vertices. In the case of …undirected graphs, an efficient polynomial-time algorithm is presented. In the case of directed graphs, we find that this problem is NP-hard. In addition, we show that it is fixed-parameter tractable with respect to the combined parameter the number of sink vertices and the number of source vertices of a graph, however, it is W[1]-hard with respect to both parameters the number of new edges and the number of input pairs. Show more

Keywords: Graph augmentation, point-to-point connectivity, strong-connectivity, bridge-connectivity, FPT-algorithm

DOI: 10.3233/FI-2018-1690

Citation: Fundamenta Informaticae, vol. 160, no. 4, pp. 447-463, 2018