Fundamenta Informaticae - Volume 4, issue 4

Authors: Szałas, Andrzej

Article Type: Research Article

Abstract: A language is considered in which the reader can express such properties of block-structured programs with recursive functions as correctness and partial correctness. The semantics of this language is fully described by a set of schemes of axioms and inference rules. The completeness theorem and the soundness theorem for this axiomatization are proved.

Keywords: algorithmic logic, Boolean algebra, completeness, correctness, filter, lattice, Lindenbaum-Tarski algebra, Q-filter, recursive functions, soundness

DOI: 10.3233/FI-1981-4411

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 975-995, 1981

Authors: Bergstra, Jan | Tiuryn, Jerzy

Article Type: Research Article

Abstract: An algebra is said to be iterative if every nontrivial finite system of fixed-point equations has unique solution. The paper discusses possibilities of finding topological structure for a given iterative algebra so that the unique solution of every system S can be approximated by a sequence of elements generated from S.

Keywords: fixed-point semantics, iterative algebras, approximations of unique fixed points

DOI: 10.3233/FI-1981-4412

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 997-1014, 1981

Authors: Gould, Jerren

Article Type: Research Article

Abstract: In Gould and Wegman (1977), a model of a system located within an environment was introduced in which the transition function of the system is not only related to the present state and input, but also to the present configuration of the environment. In this paper we shall consider the case of automata operating within random environments. In contrast to the previous case, where we suppose we can control the environment, we shall assume that the realization of the environment is governed by some probabilistic structure. Hence, the sequence of environment configurations is a stochastic process. In considering …automata in random environments (ARE) there is a dual nature to the randomness, the environment sequence is random and for each value the environment sequence assumes, the probabilistic state transitions are defined. In the ARE case the relative frequency of acceptance of a tape under a fixed random environment sequence estimates the expected acceptance probability. Accordingly, the notion of expected acceptance sets is defined. Finally, a mean equivalent canonical representation for automata in random environments which eliminates the randomness due to the probabilistic state transitions is formulated. That is, for any ARE with finite environment set, deterministic assignment of the initial state, and deterministic transitions which has a state distribution equivalent in the mean. This formulation of automata in random environments is useful when only certain probabilistic assumptions about the occurrence of any environment configuration can be made or when the environment configuration can only be measured by statistical techniques. Show more

Keywords: automaton, probabilistic automaton, automaton in environment, random environment, environmental stochastic process, simulation

DOI: 10.3233/FI-1981-4413

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 1015-1040, 1981

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: Information (storage and retrieval) systems lead to define sequents of formulas of the propositional calculus. By constructing the so called very simple information systems and their marked valuations, we prove that a formula β is a sequent of a formula α if and only if the formula β → α , is a tautology.

Keywords: information system, very simple information system, valuation, marked valuation, sequent

DOI: 10.3233/FI-1981-4414

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 1041-1048, 1981