Fundamenta Informaticae - Volume 132, issue 1

Authors: Halava, Vesa | Karhumäki, Juhani | Matiyasevich, Yuri

Article Type: Other

DOI: 10.3233/FI-2014-1028

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. v-v, 2014

Authors: Rumyantsev, Andrei | Shen, Alexander

Article Type: Research Article

Abstract: A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lovász local lemma.

DOI: 10.3233/FI-2014-1029

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 1-14, 2014

Authors: Idiatulina, Lidia A. | Shur, Arseny M.

Article Type: Research Article

Abstract: The interaction property (or the Fine–Wilf property) for periodic partial words is studied. Partial words with two periods are represented by bipartite graphs and the interaction property is related to the edge connectedness property of these graphs. Threshold functions for the edge connectedness of random bipartite graphs and multigraphs are found. As a corollary, the interaction property is described in probabilistic terms.

DOI: 10.3233/FI-2014-1030

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 15-31, 2014

Authors: Břinda, Karel | Pelantová, Edita | Turek, Ondřej

Article Type: Research Article

Abstract: The m-bonacci word is a generalization of the Fibonacci word to the m-letter alphabet 𝒜 = {0, ... ,m − 1}. It is the unique fixed point of the Pisot–type substitution �m : 0 → 01, 1 → 02, ... , (m − 2) → 0(m − 1), and (m − 1) → 0. A result of Adamczewski implies the existence of constants c(m) such that the m-bonacci word is c(m) -balanced, i.e., numbers of letter a occurring in two factors of the same length differ at most by c(m) for any letter a ∈ 𝒜. The …constants c(m) have been already determined for m = 2 and m = 3. In this paper we study the bounds c(m) for a general m ≥ 2. We show that the m-bonacci word is ($\lfloor; \kappa m \rfloor + 12$ )-balanced, where κ ≈ 0.58. For m ≤ 12, we improve the constant c(m) by a computer numerical calculation to the value $\lceil {m+1 \over 2} \rceil$ . Show more

Keywords: Balance property, m-bonacci word

DOI: 10.3233/FI-2014-1031

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 33-61, 2014

Authors: Chistikov, Dmitry | Fedorova, Valentina | Voronenko, Andrey

Article Type: Research Article

Abstract: A certificate of non-membership for a Boolean function f with respect to a class 𝒞, f ∉ 𝒞, is a set S of input strings such that the values of f on strings from S are inconsistent with any function h ∈ 𝒞. We study certificates of non-membership with respect to several classes of read-once functions, generated by their bases. For the basis {&, ∨, $\neg$}, we determine the optimal certificate size for every function outside the class and deduce that 6 strings always suffice. For the same basis augmented with a function x1 ... xs ∨ ${\bar …x}_1$ ... ${\bar x}_s$, we show that there exist n-variable functions requiring Ω(ns−1 ) strings in a certificate as n → ∞. For s = 2, we show that this bound is tight by constructing certificates of size O(n) for all functions outside the class. Show more

Keywords: certificate of non-membership, read-once function

DOI: 10.3233/FI-2014-1032

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 63-77, 2014

Authors: Dahmoune, Mohamed | El Abdalaoui, El Houcein | Ziadi, Djelloul

Article Type: Research Article

Abstract: In this paper we apply the concept of common follow sets (CFS) of a regular expression to homogeneous finite state automaton. Based on this concept and using particular binary trees, we devise an efficient algorithm to reduce (minimize) the number of transitions of the automaton recognizing the language L(En ) denoted by the regular expression $E_n = (1 + \epsiv) \cdot (2 + \epsiv) \cdot (3 + \epsiv) \dots (n+\epsiv)$ . Experiments reveal that for small values of n, all ε-free NFAs with n+1 states and with a minimum number of transitions for L(En ) are exactly those obtained …by our construction. Also, the produced ε-free NFA is asymptotically minimal, in the sense that the number of transitions is equivalent to n(log2 n)2 which corresponds in the same time to the upper and the lower bound. We conjecture that our construction is not only a reduction but a minimization for L(En ). Show more

Keywords: automata, transition, tree, reduction, minimization

DOI: 10.3233/FI-2014-1033

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 79-94, 2014

Authors: Gusev, Vladimir V. | Maslennikova, Marina I. | Pribavkina, Elena V.

Article Type: Research Article

Abstract: We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language.

Keywords: ideal language, synchronizing automaton, synchronizing word, strongly connected automaton, syntactic complexity

DOI: 10.3233/FI-2014-1034

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 95-108, 2014

Authors: Ochem, Pascal

Article Type: Research Article

Abstract: An infinite square-free word w over the alphabet Σ3 = {0, 1, 2} is said to have a k-stem σ if |σ| = k and w = σw1 w2 $\dots$ where for each i, there exists a permutation πi of Σ3 which extended to a morphism gives wi = πi (σ). Harju proved that there exists an infinite k-stem word for k = 1, 2, 3, 9 and 13 ≤ k ≤ 19, but not for 4 ≤ k ≤ 8 and 10 ≤ k ≤ 12. He asked whether k-stem words exist for …each k ≥ 20. We give a positive answer to this question. Currie has found another construction that answers Harju's question. Show more

DOI: 10.3233/FI-2014-1035

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 109-112, 2014

Authors: Itsykson, Dmitry | Sokolov, Dmitry

Article Type: Research Article

Abstract: In this paper we study heuristic proof systems and heuristic non-deterministic algorithms. We give an example of a language Y and a polynomial-time samplable distribution D such that the distributional problem (Y, D) belongs to the complexity class HeurNP but Y ∉ NP if NP ≠ coNP, and (Y, D) ∉ HeurBPP if (NP,PSamp) $\nsubseteq$ HeurBPP. For a language L and a polynomial q we define the language padq (L) composed of pairs (x, r) where x is an element of L and r is an arbitrary binary string of length at least q(|x|). If $D = \{D_n\}^\infty_{n=1}$ …is an ensemble of distributions on strings, let D × Uq be a distribution on pairs (x, r), where x is distributed according to Dn and r is uniformly distributed on strings of length q(n). We show that for every language L in AM there is a polynomial q such that for every distribution D concentrated on the complement of L the distributional problem (padq (L), D × Uq ) has a polynomially bounded heuristic proof system. Since graph non-isomorphism (GNI) is in AM, the above result is applicable to GNI. Show more

Keywords: heuristic computation, proof systems, non-deterministic algorithm, Arthur-Merlin games

DOI: 10.3233/FI-2014-1036

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 113-129, 2014

Authors: Salo, Ville | Törmä, Ilkka

Article Type: Research Article

Abstract: We study the class of word-building games, where two players pick letters from a finite alphabet to construct a finite or infinite word. The outcome is determined by whether the resulting word lies in a prescribed set (a win for player A) or not (a win for player B). We focus on symbolic dynamical games, where the target set is a subshift. We investigate the relation between the target subshift and the set of turn orders for which A has a winning strategy.

Keywords: subshifts, games, perfect information, entropy

DOI: 10.3233/FI-2014-1037

Citation: Fundamenta Informaticae, vol. 132, no. 1, pp. 131-152, 2014