Fundamenta Informaticae - Volume 6, issue 1

Article Type: Other

DOI: 10.3233/FI-1983-6101

Citation: Fundamenta Informaticae, vol. 6, no. 1, pp. i-vi, 1983

Authors: Eberbach, Eugeniusz

Article Type: Research Article

Abstract: This paper concerns a concept of selfperfecting and selflearning of digital computer systems. This idea is not new, but continuously in the state of elaborations. Such systems, i.e. with a possibility of selflearning and selfmodification would have undoubtedly greater possibilities and elastic properties in their behaviour than traditional digital systems. In the paper a digital system is treated as a complex system of algorithms. As an abstract model of real algorithms. so called Mazurkiewicz FC-algorithm is considered. FC-algorithms used in the paper have been extended to modifiable Fe-algorithms by adding a time-variant structure and the use of the notion …of tolerance spaces. This structure allowed us to introduce a model of learning for modifiable FC-algorithms. Learning is understood as a goal directed process of changes of activities on the basis of experience. Show more

Keywords: FC-algorithm – A, a modidiable FC-algorithm – MA, the ith configuration of MA – MAi, the ith function of modification – Φi, a relation of tolerance – τP, canonical sets of equations for MAi and for MA, a cost function – Ψ, an extended cost function – Ψ̅, a cost system – R, “beyond-real” numbers – R∞η, a finite learning process, a goal of learning, an optimization problem for MA, the stop-property for MA, an antigradient of the tolerance τP – ∇̅τP, a direction of the improvement, the outsider- and the inside-cost functions, a process of learning with a teacher and selflearning

DOI: 10.3233/FI-1983-6102

Citation: Fundamenta Informaticae, vol. 6, no. 1, pp. 1-44, 1983

Authors: Imieliński, Tomasz

Article Type: Research Article

Abstract: The problem of the minimization of the set of attributes (key-finding) in a given i.s.r. system is proved to be equivalent to prime implicant finding for a certain term. The equivalence between the minimalization of the set of attributes and minimal test finding is exhibited. As a consequence, minimal test finding algorithms are also applicable to the present problem.

Keywords: information storage and retrieval, information systems

DOI: 10.3233/FI-1983-6103

Citation: Fundamenta Informaticae, vol. 6, no. 1, pp. 45-51, 1983

Authors: Lipski Jr., Witold

Article Type: Research Article

Abstract: A(O,1)-matrix A is said to have the consecutive ones property if its rows can be permuted so that the 1’s appear consecutively in each column. We present four NP-complete problems connected with some generalizations of this notion. These problems concern decomposing the columns of a matrix into two subsets having the consecutive ones property, decomposing the rows into three subsets having the consecutive ones property, finding a subset of rows of maximal size having the consecutive ones property, and finding a permutation of the rows such that the 1’s in any column are contained in a set of k consecutive …rows, for a fixed “buffer size” k. Show more

Keywords: Computational complexity, NP-complete problems, matrices with the consecutive ones property, linear families of sets, file organization, consecutive retrieval property, storage space minimization

DOI: 10.3233/FI-1983-6104

Citation: Fundamenta Informaticae, vol. 6, no. 1, pp. 53-69, 1983

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: Information (storage and retrieval) systems lead to define sequents of formulas of the propositional calculus. We give necessary and sufficient conditions for a formula β to be a sequent of a formula α with respect to a given information system and/or with respect to a given information system and its given valuation.

Keywords: information system, valuation, sequent with respect to an information system, sequent with respect to an information system and its valuation

DOI: 10.3233/FI-1983-6105

Citation: Fundamenta Informaticae, vol. 6, no. 1, pp. 71-79, 1983

Authors: Goeman, H.J.M. | Groenwegen, L.P.J. | Kleijn, H.C.M. | Rozenberg, G.

Article Type: Research Article

Abstract: This paper investigates the use of sets of places of a Petri net as additional (to input places) constraints for granting concession to a transition. Various modes of using constraints give rise to various classes (of languages) of constrained Petri nets. The power of these classes is compared in the language theoretical framework.

Keywords: Petri nets, concurrency, formal languages

DOI: 10.3233/FI-1983-6106

Citation: Fundamenta Informaticae, vol. 6, no. 1, pp. 81-125, 1983