Fundamenta Informaticae - Volume 3, issue 4

Article Type: Other

DOI: 10.3233/FI-1980-3401

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. i-ix, 1980

Authors: Atanasiu, Adrian

Article Type: Research Article

Abstract: The paper deals with some C-grammars and tree-codification properties extending the result in [1]. We try to exhibit new aspects and important results, e.g. that any algebraic convolutional code is a particular case of a tree-code, as well as the finite forms of the code-sets. They can result in new methods of decodification and error correction in the case of convolutional coding.

Keywords: formal languages, algebraic coding theory, automata theory

DOI: 10.3233/FI-1980-3402

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 401-417, 1980

Authors: Sokołowski, Stefan

Article Type: Research Article

Abstract: Predicates describing the states of computation may be regarded as functions into the Boolean algebra {false, true} and programs as transformers of those functions. If we do not restrict ourselves to this algebra, we get instead terms describing the states of computation and programs transforming the terms. In many cases this approach turns out to be more natural. This paper is a mathematical study of partial correctness and termination of programs in the language of term transformations.

Keywords: semantics of programs, partial correctness, termination, calculus of relations, test relations, term transformers

DOI: 10.3233/FI-1980-3403

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 419-431, 1980

Authors: Janicki, Sławomir

Article Type: Research Article

Abstract: In the earlier paper of the author [2] it has been introduced the concept of the generability for stochastic automaton. Here we give new necessary and sufficient conditions for the generability of the set of infinite sequences of automaton states. Moreover, we consider the generability of subset, complement, union, intersection and difference of generable sets.

Keywords: stochastio automaton, probability measure, oarrier, word, language, generability, generable set

DOI: 10.3233/FI-1980-3404

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 433-444, 1980

Authors: Arnold, Andre | Nivat, Maurice

Article Type: Research Article

Abstract: The set of infinite trees is considered as an ultrametric compact space. The composition of trees is investigated. Applications to non deterministic recursive program schemes are given.

Keywords: Infinite trees, Ultrametric spaces, Algebraic semantics, Nondetermininistic programms

DOI: 10.3233/FI-1980-3405

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 445-475, 1980

Authors: Bracho, Felipe

Article Type: Research Article

Abstract: In this paper we investigate the fixed points of functions that can be obtained by continuous fixed point operators in P ω . We also introduce an operator Cgn that generates all of these fixed points for any continuous function. In the last two sections of the paper we study the fixed points of λ a . a ∘ a (retracts) and of λ y λ f . f ( ( y ) ( f ) ) (fixed point operators).

Keywords: programming language semantics, lattice, algebraic lattice, retract, continuous function, fixed points

DOI: 10.3233/FI-1980-3406

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 477-489, 1980

Authors: Gorun, Irina

Article Type: Research Article

Abstract: Following the suggestion of Prof. S. Marcus we study the “Darboux properties” of the hierarchy of intersections of context-free languages, introduced by Liu and Weiner [5]. Some properties of the Parikh function defined on an intersection of context-free languages are infered. These results are useful in proving that a certain bounded matrix language is not an intersection of context-free languages.

DOI: 10.3233/FI-1980-3407

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 491-496, 1980

Authors: Büning, Hans Kleine

Article Type: Research Article

Abstract: This paper concerns with the reachability and equality problem of generalized vector addition systems, where the systems work in the cartesian-product of the integers with finite (resp. infinite) exception set.

Keywords: generalized vector addition system, vector addition system, reachability problem, equality problem

DOI: 10.3233/FI-1980-3408

Citation: Fundamenta Informaticae, vol. 3, no. 4, pp. 497-512, 1980