Fundamenta Informaticae - Volume 2, issue 1

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