Fundamenta Informaticae - Volume 145, issue 3

Authors: Karhumäki, J. | Mazalov, V. | Matiyasevich, Yu.

Article Type: Other

DOI: 10.3233/FI-2016-1356

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. i-ii, 2016

Authors: Ananichev, Dimitry S. | Gusev, Vladimir V.

Article Type: Research Article

Abstract: The problem of approximate computation of reset thresholds of synchronizing automata has gained a lot of attention recently. We introduce a broad class of algorithms that compute reset words and analyze their approximation ratios. We present three series of automata that reveal inherent limitations of greedy strategies for approximation of reset thresholds.

Keywords: Synchronizing automata, reset threshold, synchronizing word, approximation algorithm, inapproximability, greedy algorithm

DOI: 10.3233/FI-2016-1357

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 221-227, 2016

Authors: Itsykson, Dmitry | Oparin, Vsevolod | Slabodkin, Mikhail | Sokolov, Dmitry

Article Type: Research Article

Abstract: The resolution complexity of the perfect matching principle was studied by Razborov [1], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n ) where n is the number of vertices in Gn . This lower bound is tight up to some polynomial. Our result implies the 2Ω(n ) lower bounds for the complete graph K 2n + 1 and the complete bipartite graph K n …,O (n ) that improves the lower bounds following from [1]. We show that for every graph G with n vertices that has no perfect matching there exists a resolution refutation of perfect matching principle for G of size O (n 2 2n ). Thus our lower bounds match upper bounds up to a multiplicative constant in the exponent. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d , for every n large enough, for every function h : {1, 2, . . . , n } → {1, 2, . . . , d }, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i -th vertex is at least h (i ) and at most D , and it is impossible to make all degrees equal to h (i ) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size 2Ω(n ). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph. Preliminary version of this paper appeared in proceedings of CSR-2015 [2]. Show more

Keywords: proof complexity, expander, perfect matching, resolution, width

DOI: 10.3233/FI-2016-1358

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 229-242, 2016

Authors: Junnila, Ville | Laihonen, Tero

Article Type: Research Article

Abstract: Information retrieval in associative memories was considered recently by Yaakobi and Bruck. In their model, a stored information unit is retrieved using input clues. In this paper, we study the problem where at most s (s ≥ 0) of the received input clues can be false and we still want to determine the sought information unit uniquely. We use a coding theoretical approach to estimate the maximum number of stored information units with respect to a given s . Moreover, optimal results for the problem are given, for example, in the infinite king grid. We also discuss the …problem in the class of line graphs where a characterization and a connection to k -factors is given. Show more

Keywords: Information retrieval, associative memory, robustness, Johnson bound, k-factor

DOI: 10.3233/FI-2016-1359

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 243-256, 2016

Authors: Kari, Jarkko

Article Type: Research Article

Abstract: The tiling problem is the decision problem to determine if the infinite plane can be tiled by copies of finitely many given Wang tiles. The problem is known since the 1960’s to be undecidable. The undecidability is closely related to the existence of aperiodic Wang tile sets. There is a known method to construct small aperiodic tile sets that simulate iterations of one-dimensional piecewise linear functions using encodings of real numbers as Sturmian sequences. In this paper we provide details of a similar simulation of two-dimensional piecewise affine functions by Wang tiles. Mortality of such functions is undecidable, which directly …yields another proof of the undecidability of the tiling problem. We apply the same technique on the hyperbolic plane to provide a strongly aperiodic hyperbolic Wang tile set and to prove that the hyperbolic tiling problem is undecidable. These results are known in the literature but using different methods. Show more

Keywords: Wang tiles, tiling problem, domino problem, Sturmian sequences, immortality problem, piecewise affine function, hyperbolic plane, aperiodicity

DOI: 10.3233/FI-2016-1360

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 257-277, 2016

Authors: Karpov, Dmitri V.

Article Type: Research Article

DOI: 10.3233/FI-2016-1361

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 279-312, 2016

Authors: Leri, Marina | Pavlov, Yuri

Article Type: Research Article

Abstract: We consider a random process of fire propagation over the links of the two configuration graphs with random node degrees. Node degrees follow either the power-law or the Poisson distribution. A comparative analysis of these graph models in terms of the number of nodes remaining after the fire was performed. The conditions under which this number is greater for one or the other node degree distribution were found.

Keywords: configuration random graphs, power-law distribution, Poisson distribution, robustness, forest fire model

DOI: 10.3233/FI-2016-1362

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 313-322, 2016

Authors: Matsuhisa, Takashi

Article Type: Research Article

Abstract: This paper treats subgroup Nash equilibriums which concept is given as an extension of Nash equilibrium of a strategic game with non-partitional information, and addresses the problem how to reach the equilibrium by communication through messages according to network among players. A subgroup Nash equilibrium of a strategic game consists of (1) a subset S of players, (2) independent mixed strategies for each member of S together with (3) the conjecture of the actions for the other players outside S provided that each member of S maximizes his/her expected payoff according to the product of all …mixed strategies for S and the conjecture about other players’ actions. Suppose that the players have a reflexive and transitive information with a common prior distribution, and that each player in a subgroup S predicts the other players’ actions as the posterior of the others’ actions given his/her information. He/she communicates privately his/her belief about the other players’ actions through messages to the recipient in S according to the communication network in S. We show that in the pre-play communication according to the revision process of their predictions about the other players’ actions, their future predictions converges to a subgroup Nash equilibrium of the game in the long run. Show more

Keywords: Communication, Conjecture, Message, Nash equilibrium, Protocol, Conjecture, Non-corporative game, Non partition information, S4n-knowledge model

DOI: 10.3233/FI-2016-1363

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 323-340, 2016

Authors: Mazalov, V. V. | Avrachenkov, K. E. | Trukhina, L. I. | Tsynguev, B. T.

Article Type: Research Article

Abstract: The betweenness centrality is one of the basic concepts in the analysis of the social networks. Initial definition for the betweenness of a node in the graph is based on the fraction of the number of geodesics (shortest paths) between any two nodes that given node lies on, to the total number of the shortest paths connecting these nodes. This method has polynomial complexity. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). Two approaches …are used to determine the characteristic function. In the first approach the characteristic function is determined via the number of direct and indirect weighted connecting paths in the coalition. In the second approach the coalition is considered as an electric network and the characteristic function is determined as a total current in this network. We use the Kirchhoff’s law. After that the betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network “VKontakte”, as well as the comparing with the PageRank method are presented. Show more

Keywords: betweenness centrality, weighted graph, cooperative game, social networks

DOI: 10.3233/FI-2016-1364

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 341-358, 2016

Authors: Raigorodskii, A.M.

Article Type: Research Article

Abstract: In this paper, we overview three closely related problems: Nelson–Hadwiger problem on coloring spaces with forbidden monochromatics distances; Borsuk’s problem on partitioning sets in spaces into parts of smaller diameter; problem of finding codes with forbidden Hamming distances.

DOI: 10.3233/FI-2016-1365

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 359-369, 2016

Authors: Rubinchik, Mikhail | Shur, Arseny M.

Article Type: Research Article

Abstract: We prove that a random word of length n over a k -ary fixed alphabet contains, on expectation, Θ ( n ) distinct palindromic factors. We study this number of factors, E (n , k ), in detail, showing that the limit lim n → ∞ Ε ( n , k ) / n does not exist for any k ≥ 2, lim inf n → ∞ Ε ( n , k ) / n = Θ ( 1 ) , …and lim sup n → ∞ Ε ( n , k ) / n = Θ ( k ) . Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words. Show more

DOI: 10.3233/FI-2016-1366

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 371-384, 2016

Authors: Saarela, Aleksi

Article Type: Research Article

Abstract: We study the question of what can be said about a word based on the numbers of occurrences of certain factors in it. We do this by defining a family of equivalence relations that generalize the so called k -abelian equivalence. The characterizations and answers we obtain are linear algebraic. We also use these equivalence relations to help us in solving some problems related to repetitions and palindromes, and to point out that some previous results about Sturmian words and k -abelian equivalence hold in a more general form.

DOI: 10.3233/FI-2016-1367

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 385-397, 2016

Authors: Selezneva, Svetlana N.

Article Type: Research Article

Abstract: The multiplicative complexity μ (f ) of a Boolean function f is the smallest number of & (of AND gates) in circuits in the basis {x &y , x ⊕y , 1} such that each circuit implements the function f . By μ (S ) we denote the number of & (of AND gates) in a circuit S in the basis {x &y , x ⊕ y , 1}. We present a method to construct circuits in the basis {x &y , x ⊕ y , 1} for Boolean functions. By this method, for an arbitrary …function f (x 1 , . . . , xn ), we can construct a circuit Sf implementing the function f such that μ (Sf ) ≤ (3/2 + o (1)) · 2n /2 , if n is even, and μ (Sf ) ≤ (√2 + o (1))2n /2 , if n is odd. These evaluations improve estimations from [1]. Show more

Keywords: Boolean function, circuit, complexity, multiplicative complexity, upper bound

DOI: 10.3233/FI-2016-1368

Citation: Fundamenta Informaticae, vol. 145, no. 3, pp. 399-404, 2016