Fundamenta Informaticae - Volume 8, issue 1

Article Type: Other

DOI: 10.3233/FI-1985-8101

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. i-vi, 1985

Authors: Jankowski, Andrzej W. | Rauszer, Cecylia

Article Type: Research Article

Abstract: The paper deals with the mathematical description of information systems with a limited access to a data base. Similarly as in [1] an area to which the user has access is called his priority. The information systems introduced in the paper are mathematical models for an intermediate logic with logical constants that corresponds to the priorities. The principles for operating this language are described, as well as a complete semantics is formulated.

Keywords: data base, formal language, completeness

DOI: 10.3233/FI-1985-8102

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 1-25, 1985

Authors: Janicki, Sławomir

Article Type: Research Article

Abstract: Bartoszyński raised and investigated problems of extensions and shrinkages of the Markov chain type stochastic automata (Some remarks on extensions of stochastic automata, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 18(1970), 551–556). By such an automaton we mean an ordered triple ⟨T, α , A⟩, where T denotes a finite non-empty set, α is a function from T to [0, 1] with ∑ t ∈ T α ( t ) = 1 , and A is a function T×T → [0, 1] with ∑ t ∈ T A ( …s , t ) = 1 for every s ∈ T. If an extension (shrinkage) of two automata exists, then we say that they satisfy the relation Re (Rs ). The aim of this paper is to consider some classes of automate with the same set T in which the relations Re and Rs are equivalence relations. We consider also some other relations in the class of stochastic automata. Moreover, in the first part we deal with extensions and shrinkages of probability measures. Show more

Keywords: stochastic automaton, extension of automata, shrinkage of automata, concordance of automata

DOI: 10.3233/FI-1985-8103

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 27-54, 1985

Authors: Kramosil, Ivan

Article Type: Research Article

Abstract: It is a well-known fact that binary sequences (strings) of high algorithmic complexity can be taken as good approximations of statistically independent random sequences with two equiprobable outputs. Here “sequence of high algorithmic complexity” is such one, that the length of the shortest program generating this sequence by a universal Turing machine differs only by an a priori given constant from the length of the generated sequence. The present paper generalizes this result to the case of a finite (not necessarily binary) alphabet. Considering an infinite sequence of finite sequences of high algorithmic complexity over a finite alphabet, the relative …frequency of occurences of each letter or finite string of letters is proved to tend to the inverted value of the total number of letters, or strings of letters of the given length, in question. This result may be seen as an analogy to the strong law of large numbers in the case of equiprobable probability distribution. Show more

Keywords: Pseudo-random sequences, algorithmic complexity, Turing-machines

DOI: 10.3233/FI-1985-8104

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 55-62, 1985

Authors: Zaionc, Marek

Article Type: Research Article

Abstract: In this paper term grammars are introduced. The expressing power of this grammars with variables of natural number type are just the nondeterministic programs built up without composition but with iteration of extended polynomials.

Keywords: Typed λ-calculus, nondeterministic regular programs, dynamic algebras

DOI: 10.3233/FI-1985-8105

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 63-72, 1985

Authors: Kierczak, Janusz

Article Type: Research Article

Abstract: In the paper we define the notions of the best lower and the best upper approximations of grammar, which are based on the concept of rough set introduced by Pawlak in [4]. Furthermore we give the properties of languages generated by the best lower and the best upper approximations of grammar.

Keywords: formal grammars, formal languages, rough sets, rough grammars, rough languages

DOI: 10.3233/FI-1985-8106

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 73-81, 1985

Authors: Marek, Wiktor | Pawlak, Zdzisław

Article Type: Research Article

Abstract: We study a simple model of learning process over an information system.

Keywords: learning, information system, definability

DOI: 10.3233/FI-1985-8107

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 83-88, 1985

Authors: Marek, Wiktor

Article Type: Research Article

Abstract: We present a formalization of (tuple version) of Codd’s relational model of database. The presentation stresses the ontological problems related with this model.

Keywords: Database, relational model, tuple

DOI: 10.3233/FI-1985-8108

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 89-101, 1985

Authors: Deborah, Joseph | Young, Paul

Article Type: Research Article

Abstract: In spite of the fact that much effort has been expended trying to prove lower bounds for algorithms and trying to solve the P = NP question, only limited progress has been made. Although most computer scientists remain convinced that solutions will be found, others (Hartmanis and Hopcroft, Fortune, Leivant and O’Donnell, and Phillips) have questioned the adequacy of Peano arithmetic for computer science. This uncertainty has only been increased by the recent work of Paris and Harrington showing that certain simple, finitistic, combinatorial statements are in fact independent of Peano Arithmetic. In this paper we survey complexity theoretic statements …that are known to be independent of arithmetic theories. In addition we survey recent results analyzing the arithmetic quantifier structure of computational problems. Show more

Keywords: Independence results, NP = ? coNP, P = ? NP, Peano arithmetic

DOI: 10.3233/FI-1985-8109

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 103-121, 1985

Authors: Chen, Keh-Hsun | Raś, Zbigniew W.

Article Type: Research Article

Abstract: By a homogeneous information tree we mean a tree with internal nodes labeled by attributes, edges by values of attributes and terminal nodes by sets of objects. Sets labeling terminal nodes form a partition of the set of objects classified by a homogeneous tree. Homogeneous information trees can be interpreted as models of expert systems, data bases with a menu or tree-structured data bases. The main problem we are dealing with concerns a minimization of a tree with respect to the storage cost. We propose a heuristic polynomial algorithm to construct an optimal tree.

Keywords: information tree, attributes, information retrieval, storage cost, optimization problem

DOI: 10.3233/FI-1985-8110

Citation: Fundamenta Informaticae, vol. 8, no. 1, pp. 123-149, 1985