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