Fundamenta Informaticae - Volume 7, issue 3

Article Type: Other

DOI: 10.3233/FI-1984-7301

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. i-vi, 1984

Authors: Burkhard, Hens-Dieter

Article Type: Research Article

Abstract: A certain partition of transitions in Petri Nets is characterized. This partition makes possible to construct local control which excludes global conflict.

Keywords: Petri nets, concurrency

DOI: 10.3233/FI-1984-7302

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 267-279, 1984

Authors: Enjalbert, Patrice

Article Type: Research Article

Abstract: Some links between algorithmic logic (AL) and algebraic semantics are examined. We show that the axioms of AL force the functions associated with programs to be fixpoints of the usual functionals, the ω -rule being indispensable for forcing the least one.

Keywords: order relation, continuity, fixpoint, formal computation trees

DOI: 10.3233/FI-1984-7303

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 281-300, 1984

Authors: Farinas del Cerro, Luis

Article Type: Research Article

Abstract: This paper is concerned with the relationship of termination problem for regular programs to the validity of certain formulas in modal logic.

Keywords: modal logic, termination of programs

DOI: 10.3233/FI-1984-7304

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 301-310, 1984

Authors: Jantke, Klaus P.

Article Type: Research Article

Abstract: This paper is concerned with automatic implementation of final algebras. The result states that it is possible under the condition that there is an effective procedure generating all mutually nonequivalent (in the specified algebra) terms.

Keywords: final algebras, automatic programming

DOI: 10.3233/FI-1984-7305

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 311-322, 1984

Authors: Kubica, Grażyna

Article Type: Research Article

Abstract: A formal description of LISP 1.5 data structures is proposed. Algorithmic theory of states, which included all the LISP 1.5 data structures, is defined. By means of operations of this theory we can define each operation of programming language LISP 1.5.

Keywords: LISP 1.5, algorithmic theories

DOI: 10.3233/FI-1984-7306

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 323-336, 1984

Authors: Leonarski, Dariusz

Article Type: Research Article

Abstract: Shuffle of formal languages and its properties are considered. An application of some results of the shuffle theory to decidability of deadlock and fairness problem in parallel systems is shown.

Keywords: shuffle operation, deadlock, fairness, parallel systems

DOI: 10.3233/FI-1984-7307

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 337-341, 1984

Authors: Mirkowska, Grażyna

Article Type: Research Article

Abstract: The property of finite degree of nondeterminism is not expressible by a formula and by any set of formulas in propositional algorithmic logic PAL.

Keywords: logic of programs, expressiveness, degree of nondeterminism

DOI: 10.3233/FI-1984-7308

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 343-348, 1984

Authors: Orłowska, Ewa

Article Type: Research Article

Abstract: In the paper we suggest an approach to proving global properties of structured states by using languages with special modal operators reflecting an internal structure of these states.

Keywords: program logic, modal logic

DOI: 10.3233/FI-1984-7309

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 349-355, 1984

Authors: Pliuškevičius, Regimantas

Article Type: Research Article

Abstract: A Gentzen-style axiomatization of dynamic logics is proposed. It is compared to other axiom systems for dynamic logics. Some problems of relative decidability are considered.

Keywords: dynamic logics, Gentzen-style axiomatization

DOI: 10.3233/FI-1984-7310

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 357-358, 1984

Authors: Skordev, Dymiter

Article Type: Research Article

Abstract: The paper presents an abstract tool for describing general properties of programs. Iterative combinatory space approach makes possible to transfer recursion – theoretical methods onto logical system which is constructed in this paper.

Keywords: Iterative combinatory space, normal form theorem

DOI: 10.3233/FI-1984-7311

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 359-365, 1984

Authors: Stapp, Lucjan

Article Type: Research Article

Abstract: In the last few years parallel programs are intensively studied. But when parallel program is investigated, it is assumed, that only one “cobegin … coend ” (“fork … join”) operation is used (see e.g. [1,2]) in the program schemata. In the paper we introduce the notion of the equivalence relation between parallel programs and then it is proved that it is sufficient to study properties of parallel programs only with one “cobegin … coend ” program connective.

Keywords: equivalence of parallel programs, normal form of parallel programs

DOI: 10.3233/FI-1984-7312

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 367-376, 1984

Authors: Szałas, Andrzej

Article Type: Research Article

Abstract: The fact that for every formula describing properties of programs with recursive functions there exists an equivalent while -formula with stacks is proved in a constructive way. This implies the possibility of using the algorithmic theory of stacks to prove the properties of ALGOL-like programs. The normal forms for such programs are also defined.

Keywords: algorithmic logic, algorithmic theory, block-structured program, interpretation of theories, normal forms for programs, recursive functions, relational system, translation

DOI: 10.3233/FI-1984-7313

Citation: Fundamenta Informaticae, vol. 7, no. 3, pp. 377-388, 1984