Fundamenta Informaticae - Volume 38, issue 1-2

Authors: Karhumäki, J. | Mateescu, A. | Rozenberg, G.

Article Type: Other

DOI: 10.3233/FI-1999-381218

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. i-xxii, 1999

Authors: Ben-Amram, Amir M. | Jones, Neil D.

Article Type: Research Article

Abstract: Using a simple programming language as a computational model, Neil Jones has shown that a constant-factor time hierarchy exists: thus a constant-factor difference in time makes a difference in problem-solving power, unlike the situation with Turing machines. In this note we review this result and fill in the programming details in the proof, thus obtaining a precise version of the theorem with explicit constant factors. Specifically, multiplying the running time by 232 provably allows more decision problems to be solved.

Keywords: time complexity, hierarchy theorem, universal program

DOI: 10.3233/FI-1999-381201

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

Authors: Penttonen, Martti

Article Type: Research Article

Abstract: The purpose of a model of computation is to provide the algorithm designer a device for running algorithms. It should be conceptually clear to let him or her concentrate at the algorithmic ideas for solving the problem. At the same time it should be concrete enough to give a realistic estimate on the use resources, when the algorithm is executed on a real computer. In this paper we analyze some weaknesses of existing models of computation, namely sequential access machine and random access machine, and propose a new cost model, called relative cost random access machine, which solves some contradictions …between these models. The new model actually only generalizes the way of counting the complexity, and includes sequential access machines and random access machines as special cases. At the same time, it is flexible enough to characterize the cost of memory access in current computers. Show more

Keywords: Turing machine, random access machine, cost model

DOI: 10.3233/FI-1999-381202

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 17-23, 1999

Authors: Skyum, Sven | Frandsen, Gudmund S. | Miltersen, Peter Bro | Binderup, Peter G.

Article Type: Research Article

Abstract: We prove that at least 3k−4/k(2k−3)(n/2) – O(k)equivalence tests and no more than 2/k (n/2) + O(n) equivalence tests are needed in the worst case to identify the equivalence classes with at least k members in set of n elements. The upper bound is an improvement by a factor 2 compared to known results. For k = 3 we give tighter bounds. Finally, for k > n/2 we prove that it is necessary and it suffices to make 2n − k − 1 equivalence tests which generalizes a known result for k = [n+1/2].

DOI: 10.3233/FI-1999-381203

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 25-37, 1999

Authors: Wanne, Merja | Linna, Matti

Article Type: Research Article

Abstract: The paper considers adjacency relation systems introduced by Wanne [10] (1998). The main problems studied are how to characterize the sets of relations, which uniquely define all other adjacency relations, and how one can determine whether a given set of relations satisfies this property. The paper contains the solutions of both questions. One of the goals in introducing the adjacency relation systems has been the development of a theory, which can be used to model databases.

DOI: 10.3233/FI-1999-381204

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 39-50, 1999

Authors: Bogdanović, S. | Ćirić, M. | Petković, T. | Imreh, B. | Steinby, M.

Article Type: Research Article

Abstract: Subdirect decompositions of unary algebras are studied in connection with one-element subalgebras, cores, Rees extensions of congruences of subalgebras, dense extensions and disjunctive elements. In particular, subdirectly irreducible unary algebras are described in terms of these notions.

DOI: 10.3233/FI-1999-381205

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 51-60, 1999

Authors: Nielsen, Mogens | Hune, Thomas

Article Type: Research Article

Abstract: Formal models for real-time systems have been studied intensively over the past decade. Much of the theory of untimed systems have been lifted to real-time settings. One example is the notion of bisimulation applied to timed transition systems, which is studied here within the general categorical framework of open maps. We define a category of timed transition systems, and show how to characterise standard timed bisimulation in terms of spans of open maps with a natural choice of a path category. This allows us to apply general results from the theory of open maps, e.g. the existence of canonical models …and characteristic logics. Also, we obtain here an alternative proof of decidability of bisimulation for finite transition systems, and illustrate the use of open maps in finite presentations of bisimulations Show more

DOI: 10.3233/FI-1999-381206

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 61-77, 1999

Authors: Jurvanen, Eija | Lipponen, Marjo

Article Type: Research Article

Abstract: We extend the notions of distinguishability of states, simulation and universality of string automata to tree automata of Moore type. In particular, we prove that for each finite class of tree automata satisfying certain conditions, there is a unique minimal universal tree automaton. The transfer from strings to trees brings new aspects but also adds difficulties in generalizing classical Moore results.

Keywords: tree automata, Moore experiments, distinguishability, simulation, universality

DOI: 10.3233/FI-1999-381207

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 79-91, 1999

Authors: Kari, Jarkko

Article Type: Research Article

Abstract: We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d + 2 layers can be combined into d + 1 layers. This proves that no more than d + …1 layers are necessary. We demonstrate that in the two-dimensional case d = 2 the number d + 1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers. Show more

Keywords: Cellular automata, reversible computation

DOI: 10.3233/FI-1999-381208

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 93-107, 1999

Authors: Ilie, Lucian

Article Type: Research Article

Abstract: We consider several open problems of Karhumäki, Mignosi, and Plandowski, cf. [KMP], concerning the expressibility of languages and relations as solutions of word equations. We show first that the (scattered) subword relation is not expressible. Then, we consider the set of k-power-free finite words and solve it negativelly for all nontrivial integer values of k. Finally, we consider the Fibonacci finite words. We do not solve the problem of the expressibility of the set of these words but prove that a negative answer (as believed) cannot be given using the tools in [KMP].

Keywords: word equation, subword, power-free, Fibonacci

DOI: 10.3233/FI-1999-381209

Citation: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 109-118, 1999

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