Fundamenta Informaticae - Volume 38, issue 1-2

Authors: Karhumäki, Juhani | Mantaci, Sabrina

Article Type: Research Article

Abstract: We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.

Keywords: Combinatorics on words, Defect theorem, k-ary trees

DOI: 10.3233/FI-1999-381210

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 119-133, 1999

Authors: Ruohonen, Keijo

Article Type: Research Article

Abstract: Methods are described for reducing the equivalence problem for sequences defined by recurrence equations in various finitely generated groups to polynomial Gröbner basis constructions. The methods are simple enough to allow a straigthforward implementation in computer algebra programs.

Keywords: recurrences in groups, equivalence problem, polynomial manipulation

DOI: 10.3233/FI-1999-381211

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 135-148, 1999

Authors: Ding, Cunsheng | Lam, Kwok Yan | Xing, Chaoping

Article Type: Research Article

Abstract: In this paper we present a binary-tree approach to the construction of all binary duadic codes of length n = pm . We also calculate the number of binary duadic codes of length n = pm , where p ≡ +1 (mod 8) is a prime.

Keywords: Duadic codes, cyclotomy

DOI: 10.3233/FI-1999-381212

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 149-161, 1999

Authors: Koskinen, Jukka A.

Article Type: Research Article

Abstract: This paper is a cryptographically motivated study of the knapsack, its subset sum function and its inverse relation, the decipherment function. The novelty is that the subset sum function is not assumed to be injective. Instead, various forms of “jectivity” are introduced, distinguished by the amount of subsets that are allowed to have the same sum. Besides charting several general properties of knapsacks and the functions the paper reports on experiments that looked for dense knapsacks. Also a concrete construction of a relatively dense easily decipherable knapsack is presented.

Keywords: Knapsack, subset sum, cryptography, non-injectivity

DOI: 10.3233/FI-1999-381213

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 163-180, 1999

Authors: Niemi, Valtteri | Renvall, Ari

Article Type: Research Article

Abstract: We show how a standard deck of playing cards can be used to implement a secure multiparty protocol to compute any boolean function. Our contribution to previous work: no identical copies of cards are needed, and the number of necessary cards is reduced.

Keywords: cryptographic protocols, zero-knowledge

DOI: 10.3233/FI-1999-381214

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 181-188, 1999

Authors: Halava, Vesa | Harju, Tero

Article Type: Research Article

Abstract: It is shown that the universe problem L(Aγ ) = A* is undecidable for 4-state finite automata A with integer weight function γ on its transitions. This holds even in the case, where A is acyclic and the weighting γ satisfies the unimodality condition. The language L(Aγ ) is defined as the set of words ω for which there exists a path π of A having zero weight, that is, γ(π) = 0.

Keywords: weighted finite automata, universe problem, unimodal

DOI: 10.3233/FI-1999-381215

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 189-200, 1999

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We show that it is decidable whether or not a given D0L power series and a given DF0L power series over a computable field are equal. This generalizes to power series the result of Ruohonen stating that DF0L-D0L language equivalence is decidable.

Keywords: DOL system, formal power series, decidability

DOI: 10.3233/FI-1999-381216

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 201-208, 1999

Authors: Turakainen, Paavo

Article Type: Research Article

Abstract: Regular languages are divided into equivalence classes according to the lengths of the words and both the universal and the existential equivalence of rational transductions on the set of these classes is studied. It is shown that the cardinality equivalence problem is undecidable for ϵ-free finite substitutions. The morphic replication equivalence problem is arithmetized and an application to word equations is presented. Finally, the generalized Post correspondence problem is modified by using a single inverse morphism or a single finite substitution or its inverse instead of two morphisms.

Keywords: Decidability, equivalence, morphism, morphic replication, finite substitution, word equation

DOI: 10.3233/FI-1999-381217

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 209-221, 1999