Fundamenta Informaticae - Volume 7, issue 1

Article Type: Other

DOI: 10.3233/FI-1984-7101

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. i-vi, 1984

Authors: Orlicki, Andrzej

Article Type: Research Article

Abstract: The main result of this paper is the description of the external behaviours of control automata, developing an algebra of these behaviours and making use of these behaviours to obtain the fundamental theorem of programming for the Glushkov system.

Keywords: control machine, pushdown control automata, Glushkov’s systems, fundamental programming theorem

DOI: 10.3233/FI-1984-7102

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 1-25, 1984

Authors: Skandalis, Kostas

Article Type: Research Article

Abstract: In this paper we study the notion of programmability of functions and relations in the sense of algorithmic logic. We introduce a notion of acceptable structure. In acceptable structures a programmable function is a function which is defined by an infinite recursive sequence of cases which happens to be the so called Friedman’s schema. The last notion has been introduced as a generalization of a notion of a recursive function for structures which admitt pairing system. We apply the technique of Friedman’s schemata to study programmability in fields which as we shall prove do not admitt pairing systems. We also …study some notions of effectiveness of real numbers. Show more

Keywords: programmable real function, algorithmic logic, Friedman’s schema, recursive reals

DOI: 10.3233/FI-1984-7103

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 27-56, 1984

Authors: Czech, Zbigniew

Article Type: Research Article

Abstract: An algorithm to solve the “reaching definitions” problem on reducible flow graphs is presented. It is based on the concept of a region of a flow graph, and has the worst-case time bound of O(n2 ) bit-vector operations. The algorithm is compared for time complexity with the well-known round-robin version of the iterative algorithm. The comparison shows that for every flow graph of n>2 nodes the region analysis algorithm for the “reaching definitions” problem requires in the worst case fewer bit-vector operations than the round-robin version of the iterative algorithm for the same problem.

Keywords: global program optimization, flow graph, reducibility, region analysis, depth-first spanning tree, data flow analysis, reaching definitions, time complexity

DOI: 10.3233/FI-1984-7104

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 57-76, 1984

Authors: Schöning, Uwe

Article Type: Research Article

Abstract: An infinite hierarchy of polynomial-time reducibilities is introduced which generalizes the notion of polynomial-time Turing reducibility and strong nondeterministic polynomial-time Turing reducibility.

Keywords: polynomial-time reducibility, NP-completeness, polynomial-time hierarchy

DOI: 10.3233/FI-1984-7105

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 77-81, 1984

Authors: Dassow, Jürgen

Article Type: Research Article

Abstract: We compare the description of languages by context free, Indian parallel, Russian parallel, programmed, matrix, and random context grammars with respect to the number of nonterminals.

Keywords: formal language theory, complexity of languages, regulated rewriting

DOI: 10.3233/FI-1984-7106

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 83-103, 1984

Authors: Marek, Wiktor | Pawlak, Zdzisław

Article Type: Research Article

Abstract: We apply rough sets to characterize definable subsets of the universe of the information system.

Keywords: approximation space, fuzzy sets, information systems, tolerance theory

DOI: 10.3233/FI-1984-7107

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 105-115, 1984

Authors: Rytter, Wojciech

Article Type: Research Article

Abstract: In this paper we present an application of nondeterministic multihead automata to the membership problem for trace languages. Here our result shows that regular and context-free trace languages are not very complicated. On the other hand, we make two simple observations which are the evidence that regular trace languages are very complicated from the algebraic point of view.

Keywords: trace languages, time and space complexity, nondeterministic multihead automata

DOI: 10.3233/FI-1984-7108

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 117-127, 1984

Authors: Biskup, Joachim

Article Type: Research Article

Abstract: We study operations on generalized database relations which possibly contain maybe tuples and two types of null values. The existential null value has the meaning “value at present unknown” whereas the universal null value has the meaning “value arbitrary”. For extending a usual relational operation to generalized relations we develop three requirements: adequacy, restrictedness, and feasibility. As demonstrated for the natural join as an example, we can essetially meet these requirements although we are faced with a minor tradeoff between restrictedness and feasibility.

Keywords: relational algebra, null values, relational data bases

DOI: 10.3233/FI-1984-7109

Citation: Fundamenta Informaticae, vol. 7, no. 1, pp. 129-150, 1984