Fundamenta Informaticae - Volume 5, issue 1

Article Type: Other

DOI: 10.3233/FI-1982-5101

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. i-vi, 1982

Authors: Reusch, Bernd | Szwillus, Gerd

Article Type: Research Article

Abstract: We study a term-language, which is used by the “Warsaw-School” in an abstract model for information systems. Various normal forms as well as standard expansions with respect to product terms are formulated and proved correct. It is shown that the shortest sums of so-called maximal sub-products are the shortest representations of terms and algorithms for their generation are given.

Keywords: Information system, query language, terms, normal forms

DOI: 10.3233/FI-1982-5102

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. 1-14, 1982

Authors: Schinzel, Britta

Article Type: Research Article

Abstract: It is shown that each Gödel numbering is effective sum of infinitely many pairwise incomparable Friedberg numberings, the complexity of which set of Friedberg numberings can be of any ordinal type.

Keywords: Enumerations, Gödel numbering, Friedberg numbering, translators

DOI: 10.3233/FI-1982-5103

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. 15-33, 1982

Authors: Doberkat, Ernst E.

Article Type: Research Article

Abstract: Given the input-output behavior of a stochastic automaton and a map which compares output words, optimal controls are introduced, and an explicit formula for such a control is derived by means of linear programming techniques. The second part of the paper deals with the situation in which an input and an output word are given and the probability with which the optimal control puts out the word is requested. An algorithm for computing this probability is presented and analysed with respect to its behavior in the worst and in the average case. The latter analysis develops some new techniques, which …are necessary since an uncountable variety of possible inputs has to be considered. These techniques come mainly from real analysis, in particular from measure theory. Show more

Keywords: Stochastic automata, optimal control, linear programming, analysis of algorithms, average complexity

DOI: 10.3233/FI-1982-5104

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. 35-75, 1982

Authors: Troeger, Douglas R.

Article Type: Research Article

Abstract: This paper presents a characterization of congruences on algebraic and iteration theories. The characterization is used to obtain (1) a subdirect decomposition of the free iteration theory, (2) an infinite class of subdirectly irreducible iteration theories, (3) a simple iteration theory not embeddable in the iteration theory [X, 0] of ‘partial functions’, and (4) a condition ensuring that a congruence on the algebraic theory of finite trees is the restriction of a congruence on the algebraic theory of all trees.

Keywords: algebraic and iteration theories, iterative theories, trees

DOI: 10.3233/FI-1982-5105

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. 77-100, 1982

Authors: Orłowska, Ewa

Article Type: Research Article

Abstract: A model of information systems such that data depend on a state of the system is introduced. A logic is developed enabling us to define query languages for such systems.

Keywords: information system, query language, tense logic, Boolean algebra

DOI: 10.3233/FI-1982-5106

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. 101-118, 1982

Authors: Urzyczyn, Paweł

Article Type: Research Article

Abstract: Let A be a structure with the property that every flow-chart with one stack /every recursive schema/, total over A, is strongly equivalent in A to a loop-free schema. We show that every total flow-chart with one stack can be unwound in A.

Keywords: the unwind property, flow-chart with one stack, recursive program schema

DOI: 10.3233/FI-1982-5107

Citation: Fundamenta Informaticae, vol. 5, no. 1, pp. 119-126, 1982