Fundamenta Informaticae - Volume 4, issue 2

Article Type: Other

DOI: 10.3233/FI-1981-4201

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

Authors: Müldner, Tomasz

Article Type: Research Article

Abstract: The paper examines the properties of a compilation of sequential and parallel programs with respect to computational semantics, defined in the earlier paper of the present author “On the Semantics of Parallel Programs”. A compilation of sequential programs is defined and proved to be stable, i.e. the sets of results of an arbitrary program and the corresponding compiled program coincide. Next, a natural compilation of parallel programs is defined and shown not to be stable with respect to natural semantics: The compiled program may give the results which are not results of the source program. Other semantics are …defined and it is proved that in those semantics the given compilation is stable. The main corollary states that for parallel programs with synchronizing tools, a compilation is stable in natural semantics. Show more

Keywords: Parallel programs, compilation, stable compilation

DOI: 10.3233/FI-1981-4202

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 207-243, 1981

Authors: Calude, Cristian | Pǎun, Gheorghe

Article Type: Research Article

Abstract: According to (Benson, 1970), a syntax is a category of strings and derivations (modulo similarity) between them. In this paper the semantic domain is an elementary topes. Thus, an interpretation of a syntax is a cofunctor taking strigs to products and derivations to morphisms. It is proved the existence of a free x – category U such that every syntax is a full subcategory of U , which can be determined recursively. Every interpretation of a syntax is the restriction of the interpretation of U .

DOI: 10.3233/FI-1981-4203

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 245-254, 1981

Authors: Müldner, Tomasz

Article Type: Research Article

Abstract: The paper is a continuation of the papers of the present author in which the semantics of parallel programs and several synchronizing tools (e.g. critical regions) for parallel programs were defined. Now, a universal synchronizing tool – a monitor, with delay, continue and delcont instructions, is defined. Then, an implementation of a monitor in the LOGLAN 77 programming language is given and proved to be correct. The implementation is given by means of a LOGLAN type Parallel in such a way that in order to use monitors in the user’s program it is sufficient to prefix that program …by the Parallel. Show more

Keywords: Parallel programs, synchronizing tool, monitor

DOI: 10.3233/FI-1981-4204

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 255-276, 1981

Authors: Miglioli, Pierangelo | Ornaghi, Mario

Article Type: Research Article

DOI: 10.3233/FI-1981-4205

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 277-341, 1981

Authors: Przyłuski, Wojciech

Article Type: Research Article

Abstract: The paper presents a logic which is an algorithmic extension of the classical predicate calculus and is based on the ideas given by F. Kröger. The programs and the effects of their execution are the formulas of this logic which are considered at any time scale. There are many interesting properties of the logic which are connected with the notion of time scale. These properties are examined in the paper. Moreover the problem of the formulas normalization is presented. Our logic is compared with the algorithmic logic introduced by A. Salwicki. Next, the usefulness of a new …logic in the theory of programs is shown. Show more

Keywords: thickness of formulas, algorithmic logic, algorithmic properties

DOI: 10.3233/FI-1981-4206

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 343-367, 1981

Authors: Ruohonen, Keijo

Article Type: Research Article

Abstract: An analogy to a result of J. Berstel’s and M. Nielsen’s, showing how equality of coefficient sets of certain N-rational sequences (DOL growth sequences) manifests itself by forcing equal periodical subsequences, is obtained for sequences of words. As applications, certain decidability problems for L languages are reduced to the equivalence problem for HDOL sequences.

Keywords: Developmental systems, decidability

DOI: 10.3233/FI-1981-4207

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 369-400, 1981

Authors: Vermeir, Dirk | Savitch, W.J.

Article Type: Research Article

DOI: 10.3233/FI-1981-4208

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 401-418, 1981

Authors: Truszczyński, Mirosław

Article Type: Research Article

Abstract: Algorithmic aspects of the problem of minimizing the set of attributes in an information system are considered. Two simplifications of this problem are proved to be NP-complete. A simple heuristic algorithm is presented and analyzed.

Keywords: Information system, attribute, combinatorial problems, NP-completeness, heuristic algorithms

DOI: 10.3233/FI-1981-4209

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 419-425, 1981

Authors: Grabowski, Jan

Article Type: Research Article

Abstract: The paper studies the behavior of control structures of algorithms designed for (partly) parallel execution. A generalization of Peterson’s computation sequence set, the partial language, is discussed, which reflects the concurrency of events. In particular, the families of partial languages definable by Petri nets and by safe Petri nets are investigated with respect to closedness under certain operations. Trace languages (Mazurkiewicz) and path expressions (Campbell and Habermann) are included in the considerations.

Keywords: Computation sequence set, partial word, partial language, concurrent processes, Petri net, path expression, trace language

DOI: 10.3233/FI-1981-4210

Citation: Fundamenta Informaticae, vol. 4, no. 2, pp. 427-498, 1981