Fundamenta Informaticae - Volume 145, issue 3

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