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