Fundamenta Informaticae - Volume 2, issue 1

Article Type: Other

DOI: 10.3233/FI-1978-2101

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. i-vi, 1978

Authors: Orłowska, Ewa

Article Type: Research Article

Abstract: A resolution-style theorem proving system for the ω + -valued Post logic is developed. The soundness and the completeness of the system are proved. The two versions of the Herbrand theorem for the logic considered are given.

Keywords: theorem proving, resolution, ω+-valued Post logic, Herbrand theorem, semantic tree

DOI: 10.3233/FI-1978-2102

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 1-15, 1978

Authors: Jaegermann, Michał

Article Type: Research Article

Abstract: In the paper is developed a theory of information storage and retrieval systems which arise in situations when a whole possessed information amounts to a fact that a given document has some feature from properly chosen set. Such systems are described as suitable maps from descriptor algebras into sets of subsets of sets of documents. Since descriptor algebras turn out to be pseudo-Boolean algebras, hence an “inner logic” of our systems is intuitionistic. In the paper is given a construction of systems and are considered theirs properties. We will show also (in Part II) a formalized theory of such systems.

Keywords: information retrieval, intuitiouistic logic, pseudo-Boolean algebras

DOI: 10.3233/FI-1978-2103

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 17-41, 1978

Authors: Konikowska, Beata

Article Type: Research Article

Abstract: A continuous information (c.i.) system is an informational system in which every object is described by a vector of functions of real variable. In the special case where all these functions are constant the c.i. system is equivalent to the information storage and retrieval (i.s.r.) system defined by Marek and Pawlak in [3]. The paper deals with a description language for a c.i. system. The structure of this language is analogous to the structure of the description language for i.s.r. systems introduced in [3]. Terms represent properties of objects, and formulas are statements about the system. All terms are built …by means of Boolean operations from terms representing properties of the type (a j x )(I ) ⊂ A , where a j x is the j th function describing the object x , I is an open interval or a point of the real line, and A is an arbitrary subset of the codomain of a j x . The axioms for the description language together with an inference rule are given. The valuation of terms and formulas is defined and the adequacy theorem is proved. Basing on a certain normal form theorem and the properties of a special system S max , the completeness theorem is finally proved. Show more

Keywords: continuous information system, object, description, term, formula

DOI: 10.3233/FI-1978-2104

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 43-61, 1978

Authors: Traczyk, Tadeusz

Article Type: Research Article

Abstract: The notion of numerical characterization of Boolean algebras and coproducts are used to define information systems and to develop the theory of such systems.

Keywords: numerical characterization, coproduct, full set of measures, stochastic extension

DOI: 10.3233/FI-1978-2105

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 63-70, 1978

Authors: Radziszowski, Stanisław

Article Type: Research Article

Abstract: We define the time-complexity of programs (FS -expressions) in an arbitrary relational system. We extend these notions to nondeterministic programs (NFS -expressions). There are some sufficient conditions for a relational system which ensure the equivalence of the P = N P problem in that system to the classical P = N P problem for Turing machines. This implies that the P = N P problem can be solved in thc theory of programs in some relational systems.

Keywords: time complexity, Turing machine, programmability, nondeterminism

DOI: 10.3233/FI-1978-2106

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 71-82, 1978

Authors: Grabowski, Michał

Article Type: Research Article

Abstract: By a net (in a sense of Blikle) we mean a complete lattice with a continuous and distributive semigroup operation called composition. The paper contains an investigation of algebraic properties of nets and Mazurkiewicz algorithms over nets. The free objects and the amalgamation property are analysed. It is proved (on the basis of an appropriate theorem from the theory of formal languages) that a certain equivalence of schemas of finite-control Mazurkiewicz algorithms is not partially solvable.

Keywords: lattice ordered semigroups, equivalence of Mazurkiewicz algorithms

DOI: 10.3233/FI-1978-2107

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 83-101, 1978

Authors: Tiuryn, Jerzy

Article Type: Research Article

Abstract: This paper introduces a class of algebras (called the class of regular algebras), in which the algebra of regular trees (unfoldments of monadic program schemes) is an initial algebra. This means that we have for the above-mentioned class “semantics” of monadic program schemes. We show how to treat, in a unified way, such concepts as: monadic and recursive monadic program schemes, regular and context-free languages. On the other hand, the investigation of the properties of regular algebras may be of intrinsic interest, in particular this leads to a very nice generalization of the notion of a polynomial in an …algebra. These “new” polynomials, in general, are determined by infinitely long expressions, and existence of such polynomials in the class of regular algebras is closely connected with the property that every finite tuple of algebraic mappings has a least fixed-point which is obtainable as a least upper bound of a denumerable chain of “approximations”. Show more

Keywords: regular algebras, fixed-points, generalized polynomials, program schemata, theory of computation

DOI: 10.3233/FI-1978-2108

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 103-127, 1978

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: In the paper a formalism is suggested for describing non-sequential processes. Processes are defined in this formalism by finite sets of rules. Such sets, called algorithms, consist of rules which indicate how relations between occurring objects may change (in general concurrently). They constitute a language of algorithms. Mathematical semantics of two types are formulated for this language. Ones, called objective, give descriptions of executions of algorithms in terms of objects which really exist in these executions. Other, called subjective, offer descriptions from the point of view of an observer. It is shown that objective semantics can be modelled in subjective …ones. Show more

Keywords: algorithm, execution, objective semantics, subjective semantics

DOI: 10.3233/FI-1978-2109

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 129-139, 1978

Authors: Jaegermann, Michał

Article Type: Research Article

DOI: 10.3233/FI-1978-2110

Citation: Fundamenta Informaticae, vol. 2, no. 1, pp. 141-166, 1978