Fundamenta Informaticae - Volume 4, issue 4

Article Type: Other

DOI: 10.3233/FI-1981-4401

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

Authors: Nijholt, Anton

Article Type: Research Article

Abstract: An overview is given of cover results for normal forms of regular grammars. Due to the special form of regular grammars and due to the results which are obtained it is sufficient to consider covering grammars in Greibach normal form. Among other things it is proved that any left-regular grammar can be left covered with a context-free grammar in Greibach normal form. All the cover results concerning the left- and right-regular grammars are listed, with respect to several types of covers, in a cover table.

Keywords: regular grammars, covers, Greibach normal form, parsing

DOI: 10.3233/FI-1981-4402

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 761-776, 1981

Authors: Raś, Zbigniew

Article Type: Research Article

Abstract: This paper is the second of the three parts of the work on the information retrieval systems proposed by Salton (see [13]). The system is defined by the notions of a partially ordered set of requests (A, ⩽), the set of documents X and a monotonic retrieval function U : A → 2X . Different conditions imposed on the set A and a function U make it possible to obtain various classes of information retrieval systems. We investigate systems in which (A, ⩽) is a partially ordered set, a lattice, a pseudo-Boolean algebra and a Boolean algebra. In my paper …these systems are called partially ordered information retrieval systems (po-systems), lattice information retrieval systems (l-systems), pseudo-Boolean information retrieval systems (pB-systems) and Boolean information retrieval systems (B-systems). The first part concerned po-systems and l-systems. The second part deals with pB-systems and B-systems. In the third part systems with a partial access are investigated. The present part discusses the pB-systems and B-systems. The problems connected with the properties of sets of attributes are investigated. The method of constructing a selective system for a pB-system and a B-system is given. The problem related to the minimalization of systems are investigated. Show more

Keywords: information retrieval, selectivity, artificial attributes, single systems, pB-systems, B-systems

DOI: 10.3233/FI-1981-4403

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 777-818, 1981

Authors: Urzyczyn, Paweł

Article Type: Research Article

Abstract: In the present paper we investigate algorithmically trivial structures, that is structures where every recursive function (relation) is definable by a first-order open formula. We prove that algorithmic triviality is equivalent to a property called the unwind property. We also study the notion of effective interpretation of structures and its relation to algorithmic triviality.

Keywords: algorithmic triviality, unwind property, effective interpretation, effective definitional schema

DOI: 10.3233/FI-1981-4404

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 819-849, 1981

Authors: Bergstra, Jan | Tiuryn, Jerzy

Article Type: Research Article

Abstract: We define a reducibility relation ⩽ between algebraic structures A ⩽ B means that A can be embeddet in an enrichment of B with partial computable operations. This notion is a generalized version of implementability as known in the theory of algebraic data types.

Keywords: algorithmic degrees, program schemes, programmability in algebraic structures

DOI: 10.3233/FI-1981-4405

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 851-861, 1981

Authors: Tiuryn, Jerzy

Article Type: Research Article

Abstract: In this paper we are studying two notions of continuity, both are weaker than the well known and broadly applied notion of ω -continuity. The paper shows that power set algebras of finite/infinite trees provide all possible instances of the above-mentioned continuities, which depend on the signature of trees and on the substitution: OI or IO.

Keywords: regular algebras, fixed-point equations, ω-continuity infinite trees

DOI: 10.3233/FI-1981-4406

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 863-890, 1981

Authors: Janicki, Sławomir

Article Type: Research Article

Abstract: In this note we consider a nonhomogeneous Markov chain type stochastic automaton which is a generalization of Bartoszyński’s stochastic automaton. The latter is a generalization of the Pawlak’s known machine in a stochastic direction. By nonhomogeneous stochastic automaton we mean a system ⟨ T, α , {A(n) , n ⩾ 1}⟩, where T is a finite nonempty set, α , is an initial distribution on T, and {A(n) , n ⩾ 1} is a matrix sequence whose every element is a stochastic matrix called a transition probability matrix. If A(n) = A for all n ⩾ 1, then we …obtain Bartoszyński’s automaton. The sequence (ti0 , ti1 , …), tij ∈ T, j = 0, 1, 2, … is called a word of automata if α (ti0 ) > 0 and A(k) (tik-1 , tik ) > 0 for every k ⩾ 1. The goal of this note is to give necessary and sufficient conditions for the existence of an extension and a shrinkage of the automata under consideration. These problems for T, A were considered for the first time by Bartoszyński. The shrinkage problem deals with the existence of a stochastic automaton which generates only all sequences of states of T which are simultaneously generated by two given automata while the extension problem treats of the existence of a stochastic automaton which generates all sequences of states of which are generated by at least one of two given automata. Moreover, we introduce some new notions: attainable state, concordance of automata in a wide and a narrow sense, which help us to solve the problems mentioned above. Show more

Keywords: nonhomogeneous stochastic automaton, attainable states, concordance of automata in a narrow sense, concordance in a wide sense of automata, extension of automata, shrinkage of automata

DOI: 10.3233/FI-1981-4407

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 891-917, 1981

Authors: Hajek, Petr | Kůrka, Petr

Article Type: Research Article

Abstract: A second-order axiomatization of dynamic logic with array assignments is presented. This axiomatization is shown to be arithmetically complete in the sense of Harel. As an example, a partial correctness assertion concerning a sorting algorithm is proved.

Keywords: dynamic logic, ari thmetical completeness, second-order axiomatization

DOI: 10.3233/FI-1981-4408

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 919-933, 1981

Authors: Bergstra, Jan A. | Meyer, John J.Ch.

Article Type: Research Article

Abstract: In [2] Jerzy Tiuryn has introduced Logic of Effective Definitions (LED) in which properties of effective definitional schemes are expressed. With respect to the quantifier-free part of it, he proved that each open formula is equivalent to one in a special conjunctive normal form. We prove that there is no finite bound to the number of conjuncts required for these normal forms.

Keywords: algorithmic logic, computability, algebraic structures, functional effective definitional schemes

DOI: 10.3233/FI-1981-4409

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 935-955, 1981

Authors: Pallo, Jean Marcel

Article Type: Research Article

Abstract: This paper shows that among the transformations which have words formed with three operators and four variables correspond to words formed with two operators and three variables, distributivity clone verifies some remarkable properties. Indeed, it is a confluent and noetherian relation which satisfies an inductive comparison theorem. One can deduce a computer – programmable algorithm which makes it possible to solve the word problem in a set of variables with two associative operators one of which is distributive on the right with respect to the other, i.e. to decide whether or not two words composed of variables and operators can …be proved equal as a consequence of the identities of associativity and distributivity satisfied by these operators. Show more

Keywords: word problem, magmas, confluent relation, noetherian relation

DOI: 10.3233/FI-1981-4410

Citation: Fundamenta Informaticae, vol. 4, no. 4, pp. 957-973, 1981

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