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

Authors: Reusch, Bernd | Detering, Lothar

Article Type: Research Article

Abstract: It is shown that various well-known normal forms for Boolean functions can be derived from a very general representation of subfunctions. Another general theorem on the relation between the prime implicants of a function and the prime implicants of its subfunctions is used to prove correct various methods of generating prime implicants.

Keywords: Boolean functions, prime implicants, subfunctions

DOI: 10.3233/FI-1978-2111

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

Authors: Ehrenfeucht, Andrzej | Rozenberg, Grzegorz

Article Type: Research Article

Abstract: A notion of a DOL system with rank is introduced. It provides a structural characterization of polynomially bounded DOL systemso Several consequences of such a characterization are studied.

DOI: 10.3233/FI-1978-2112

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

Authors: Meyers, Wiliam James

Article Type: Research Article

Abstract: A topological sorting of a tree is a linear ordering of its elements that preserves and extends their partial ordering in the tree. Any such arrangement of tree elements has a characteristic property, involving collective weights of initial or final substrings. Such properties have been investigated in connection with random walks, combinatorial arrangements, and the well-formed strings of parenthesis-free notations. Topological sortings of directed acyclic graphs exhibit a similar structure.

Keywords: tree, plane tree, binary tree, topological sorting, partial order, universal order, linear order, parenthesis-free notation, well-formed formula, well-formed string, ballot sequence, Polish string, Polish notation, level notation, consistent notation, universal order notation

DOI: 10.3233/FI-1978-2113

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

Authors: Lodi, E. | Luccio, F. | Mugnai, C. | Pagli, L.

Article Type: Research Article

Abstract: Two-dimensional sequential data organization is considered, where each dimension corresponds to one of two attributes. A query on the data is a figure on the storage. The elementary figure is a rectangle, and any figure can be described by a set of rectangles. Prime rectangles are defined as the ones relevant to any figure description, and the problem of finding a minimal description is studied. In particular, the upper bound to the number of prime rectangles is derived, and a cubic algorithm to find all such rectangles is given. Descriptions composed of all disjoint rectangles are …the subject of the second part or this paper. Show more

Keywords: information storage and retrieval, bidimensional memory, figure description, minimal description, prime rectangle

DOI: 10.3233/FI-1978-2114

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

Authors: Lipski Jr., Witold

Article Type: Research Article

Abstract: A new method of organizing an information storage and retrieval system is proposed and theoretically evaluated. The method uses a special normal form into which the queries entering the system are transformed. This normal form enables one to determine easily the decomposition of the set of records relevant to a query into the minimal number of segments of records stored in consecutive storage locations, and to compute the addresses of the beginning and end of each of these segments.

Keywords: information retrieval, file organization, consecutive retrieval, normal forms for queries

DOI: 10.3233/FI-1978-2115

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

Authors: Lipski Jr., Witold | Lodi, Elena | Luccio, Fabrizio | Mugnai, Cristina | Pagli, Linda

Article Type: Research Article

Abstract: Following a previous Part I, two-dimensional sequential data organization is considered. A set of data is a figure on the storage. The elementary figure is the rectangle , and any figure is described by a set of rectangles. The decomposition of a figure into disjoint rectangles is studied. Some properties of the description composed of the minimum number of disjoint rectangles (MDD) are presented. It is shown that aligned edges of a figure play a fundamental role in the form of an MDD, and an algorithm is presented which constructs an MDD of an arbitrary figure in polynomial time.

Keywords: information storage and retrieval, bidimensional memory, figure description, minimal disjoint description, aligned edges, computational geometry

DOI: 10.3233/FI-1978-2116

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

Authors: Sysło, Maciej M. | Iri, Masao

Article Type: Research Article

Abstract: This paper describes an efficient algorithm for finding whether a graph G has an outerplanar embedding in the plane. The algorithm is a realization of an inductive characterization of outerplanar graphs and uses depth-first search for coding a structure of a graph which is represented by adjacency lists. The algorithm has O (V ) time and space bounds, where V is the number of vertices in G .

Keywords: algorithm, complexity, depth-first search, embedding, graph, outerplanarity, palm tree, spanning tree

DOI: 10.3233/FI-1978-2117

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

Authors: Dańko, Wiktor

Article Type: Research Article

Abstract: In this paper we consider recursive implicit definitions of functors and predicates in algorithmic logic [1], [5], [9], which may be regarded as procedures (compare A. Salwicki [10]). We examine the possibility of elimination of defined symbols from algorithmic formulas. We prove that the halting property of a procedure is not definable by means of formulas of extended algorithmic logic [1] (with classical quantifiers). As corollary we obtain that extended algorithmic logic has not Beth-property.

Keywords: algorithmic logic, definability in algorithmic logic, implicit definitions, essentiality of procedures, halting property

DOI: 10.3233/FI-1978-2118

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

Authors: Janicki, Ryszard

Article Type: Research Article

Abstract: In this paper two methods of proving properties of programs with coroutines are presented. Both of these methods are based on a mathematical model which was defined in [3] and extended in [4], and which is called a vector of coroutines. In the case of the first method, the vector semantics is given by the least solution of an appropriate set of equations. This set of equations is constructed on the basis of the form of the whole vector. In the case of the second method, a suitable alphabet and a suitable language are associated with each of the vector …components (each component corresponds to one coroutine of the program), and the intersection of these languages is interpreted as a description of the vector semantics. The theorem on the replacement of components by equivalent (in a special sense) components is proved. Show more

Keywords: coroutine, vector of coroutines, algorithm, net, language, semantics, relation

DOI: 10.3233/FI-1978-2119

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

Authors: Tiuryn, Jerzy

Article Type: Research Article

Abstract: This paper is a continuation of Tiuryn [16]. The main notion presented in the latter paper is the notion of a regular algebra. As it was proved in Tiuryn [16] for an arbitrary signature Σ the algebra of regular Σ-trees is an initial regular algebra. This means that there are naturally defined “polynomials” for regular algebras, which are determined by infinitely long expressions. The aim of this paper is to investigate this phenomenon.

Keywords: fixed-points, generalized polynomials, recursive program schemes

DOI: 10.3233/FI-1978-2120

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

Authors: Maggiolo-Schettini, A. | Uccella, G.

Article Type: Research Article

Abstract: A language for operation on a stack (SOL) is defined formally, also from the semantic point of view. The semantics is an input-output semantics which uses functions from sequences (of integers) of indefinite length to sequences (of integers) of indefinite length as models of the computation on a stack. The programs in SOL are interpreted in recursive systems of functional definitions to which fixed point theory easily applies in order to evaluate the functions computed by the programs. The language has been implemented and used for didactic purposes.

Keywords: Programming languages, stack functions fixed point semantics

DOI: 10.3233/FI-1978-2121

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

Authors: Konikowska, Beata | Traczyk, Tadeusz

Article Type: Research Article

Abstract: For a class of stochastic information systems a query language is defined and the completeness property proved. It is also shown that each term may be transformed into a canonical form, and in some special case into a normal additive form.

Keywords: information storage and retrieval, query language, Boolean numerical algebra, stochastic information, normal form, completeness property

DOI: 10.3233/FI-1978-2122

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