Fundamenta Informaticae - Volume 4, issue 1

Article Type: Other

DOI: 10.3233/FI-1981-4101

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. i-xii, 1981

Authors: Manca, Vincenzo

Article Type: Research Article

Abstract: A natural notion of computational formalism is here characterized by elaborating on the algebraic approach with Uniformly Reflexive Structures. Namely by dealing with the undefined within a first-order theory admitting partial functions. Here, quite generally, we obtain several limitative theorems about the computational formalisms.

Keywords: Computational formalisms, uniformly reflexive structures, idealized theories, limitative theorems

DOI: 10.3233/FI-1981-4102

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 3-18, 1981

Authors: Danecki, Ryszard

Article Type: Research Article

Abstract: Closure properties of binary ETOL-languages are investigated by means of multiple tree automata. Decidability of the equivalence problem of deterministic binary ETOL-systems is proved.

Keywords: ETOL-system, multiple tree automata, deterministic ETOL-system

DOI: 10.3233/FI-1981-4103

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 19-34, 1981

Authors: Müldner, Tomasz

Article Type: Research Article

Abstract: The paper deals with the semantics of parallel programs. It is shown that there exist other semantics besides the well-known one, which reflects multiplexing and is defined as an interleaving of elementary actions. Those semantics are not necessarily equivalent with respect to the input (out-put) relation; moreover, they permit the investigation of the internal behaviour of a computation. A formalized language of parallel programs is defined. Definitions of computational semantics and of a tree of acceptable computations are given. As an example of computational semantics the semantics MULT (for multiplexing) is defined. Next a scheme of computational semantics is …introduced. Given the scheme, one can define various computational semantics by means of several strategies. The most natural scheme of computational semantics is then given, followed by examples defined by it. Connections between different classes of computational semantics are examined. Show more

Keywords: Semantics of parallel program, acceptable computation

DOI: 10.3233/FI-1981-4104

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 35-81, 1981

Authors: Ausiello, Giorgio | d’Atri, Alessandro | Protasi, Marco

Article Type: Research Article

Abstract: The ordering among classes of isomorphic NP-complete optimization problems is studied from a lattice theoretic point of view. It is shown that the set of such classes has the structure of an upper semilattice; while a top element can found be it is proved that no bottom element can exist.

Keywords: Computational complexity, lattice, NP-complete problems, optimization problems

DOI: 10.3233/FI-1981-4105

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 83-94, 1981

Authors: Müldner, Tomasz

Article Type: Research Article

Abstract: The paper contains precise and structured definitions of the following synchronizing tools: Mutually Excluding Regions, Elementary Critical Regions and Critical Regions. Some applications of these tools are shown on the following examples: the Kung algorithm of finding a zero of a function, ticket booking system, and synchronous and asynchronous Jacobi algorithms of solving a system of linear equations. Next, the implementations of the above synchronizing tools in the formal languages of parallel programming are given. The semantics of these languages are defined on the ground of the present author’s earlier paper “On the Semantics of Parallel Programs”. The implementations …are proved to be correct. The implementation of a critical region is actually an implementation of Dijkstra P and V operations on binary semaphores. Show more

Keywords: Synchronizing tool, critical region, mutual exclusion, accessibility, passive waiting, monotonicity

DOI: 10.3233/FI-1981-4106

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 95-133, 1981

Authors: Albert, J. | Maurer, H.A. | Ottmann, Th.

Article Type: Research Article

Abstract: We present necessary and sufficient conditions for an OL form F to generate regular languages only. The conditions at issue can be effectively checked, whence the “regularity problem for OL forms” is proven decidable.

Keywords: OL forms, regional languages, decision procedure

DOI: 10.3233/FI-1981-4107

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 135-149, 1981

Authors: Miglioli, Pierangelo | Ornaghi, Mario

Article Type: Research Article

Abstract: The aim of this paper is to provide a general explanation of the “algorithmic content” of proofs, according to a point of view adequate to computer science. Differently from the more usual attitude of program synthesis, where the “algorithmic content” is captured by translating proofs into standard algorithmic languages, here we propose a “direct” interpretation of “proofs as programs”. To do this, a clear explanation is needed of what is to be meant by “proof-execution”, a concept which must generalize the usual “program-execution”. In the first part of the paper we discuss the general conditions to be satisfied by …the executions of proofs and consider, as a first example of proof-execution, Prawitz’s normalization. According to our analysis, simple normalization is not fully adequate to the goals of the theory of programs: so, in the second section we present an execution-procedure based on ideas more oriented to computer science than Prawitz’s. We provide a soundness theorem which states that our executions satisfy an appropriate adequacy condition, and discuss the sense according to which our “proof-algorithms” inherently involve parallelism and non determinism. The Properties of our computation model are analyzed and also a completeness theorem involving a notion of “uniform evaluation” of open formulas is stated. Finally, an “algorithmic completeness” theorem is given, which essentially states that every flow-chart program proved to be totally correct can be simulated by an appropriate “purely logical proof”. Show more

Keywords: Proof-executions, pseudo-truth-sets, uniform evaluations, algorithmic completeness of proofs

DOI: 10.3233/FI-1981-4108

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 151-172, 1981

Authors: Fischer, Thomas R.M.

Article Type: Research Article

Abstract: The paper deals with the problem of constructing binary search trees that are available in the case of unknown or time varying access probabilities.

Keywords: Binary search tree, weighted path length, Shannon’s entropy, inaccuracy, universal binary search tree

DOI: 10.3233/FI-1981-4109

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 173-184, 1981

Authors: Paun, Georghe

Article Type: Research Article

Abstract: It is proved that the λ -rules increase the generative capacity of context-free simple matrix grammars but can be eliminated from right-linear simple matrix grammars and from linear simple matrix grammars without diminishing their generative capacity.

Keywords: Simple matrix grammars, λ-rules, index

DOI: 10.3233/FI-1981-4110

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 185-195, 1981

Authors: Rozenberg, Grzegorz | Vermeir, Dirk

Article Type: Research Article

Abstract: An infinite hierarchy within the class of ETOL languages is proved in such a way that it is spanned on an infinite sequence of ETOL languages with increasing rank where each of the languages has a length set containing the range of a strictly growing polynomial of degree 1.

DOI: 10.3233/FI-1981-4111

Citation: Fundamenta Informaticae, vol. 4, no. 1, pp. 197-205, 1981