Fundamenta Informaticae - Volume 16, issue 3-4

Article Type: Other

DOI: 10.3233/FI-1992-163-401

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. i-vii, 1992

Authors: Broy, Manfred

Article Type: Research Article

Abstract: The semantics of a simple language for describing tightly coupled “synchronous” systems is defined in terms of action structures representing histories of computations with explicit concurrency. An operational semantics is defined by term rewriting rules labelled by action structures. A consistent denotational semantics in terms of action structures is defined based on the concept of observable behaviour and on fixpoint theory. A fully abstract denotational semantics is given. In particular, the issue of interleaving semantics versus semantics including explicit concurrency is discussed.

DOI: 10.3233/FI-1992-163-402

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 201-229, 1992

Authors: Balbiani, Philippe

Article Type: Research Article

Abstract: The beauty of modal logics and their interest lie in their ability to represent such different intensional concepts as knowledge, time, obligation, provability in arithmetic, … according to the properties satisfied by the accessibility relations of their Kripke models (transitivity, reflexivity, symmetry, well-foundedness, …). The purpose of this paper is to study the ability of modal logics to represent the concepts of provability and unprovability in logic programming. The use of modal logic to study the semantics of logic programming with negation is defended with the help of a modal completion formula. This formula is a modal translation of Clack’s formula. It …gives soundness and completeness proofs for the negation as failure rule. It offers a formal characterization of unprovability in logic programs. It characterizes as well its stratified semantics. Show more

DOI: 10.3233/FI-1992-163-403

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 231-262, 1992

Authors: Novotný, Jiří | Novotný, Miroslav

Article Type: Research Article

Abstract: The concept of the relation of dependence between sets of attributes of an information system is studied in a more abstract setting – in the algebraic structure called dependence space. Complete characterization of dependence relation in a dependence space is presented.

DOI: 10.3233/FI-1992-163-404

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 263-273, 1992

Authors: Novotný, Miroslav | Pawlak, Zdzisław

Article Type: Research Article

Abstract: A set Y of attributes of an information system is said to be dependent on a set X of attributes if the classification of objects defined by X is finer or as fine as the classification defined by Y . An important problem reads as follows. If Y depends on X find a minimal X ′ ⊆ X such that Y depends on X ′ . A set X ′ is said to be a reduct of …X if X ′ is a minimal subset of X defining the same classification of objects as X . The paper is devoted to the study of relationship between reducts and dependence. Both dependence and reducts can be defined in the so called dependence spaces and the above mentioned problem can be transformed into the problem of constructing reducts in a suitable dependence space. We also present some algorithms providing reducts in a dependence space; in this way, we obtain an algorithmic solution of our problem. Show more

Keywords: information system, dependence space, reduct, dependence

DOI: 10.3233/FI-1992-163-405

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 275-287, 1992

Authors: Gorrieri, Roberto

Article Type: Research Article

Abstract: The problem of relating system descriptions at different levels of abstraction is studied in the field of Process Description Languages, following the so-called interleaving approach. Since we believe that several different languages should be used profitably during the hierarchical specification process, we investigate the problem of implementing a calculus into another one. As a case study, we introduce a pair of languages which will be increasingly enriched. The basic languages are sequential and nondeterministic; their first enrichment is obtained by adding an operator for asynchrony; then also communication is added, and finally restriction is dealt with. For each pair, the …latter language extends the former with atomicity, obtained by adding to the signature of the former an operator of strong prefixing that makes atomic the execution of a sequence of actions. The two languages are intended to be a specification and an implementation language, respectively. To directly relate them, a mapping, called atomic linear refinement, is introduced from actions of the former to atomic sequences (i.e. sequences of actions built with strong prefixing) of the latter. An atomic linear refinement can be homomorphically extended to become a mapping among process terms of the two languages and thus also among the states of their associated transition systems. A notion of implementation, based on a sort of bisimulation (parametric with respect to an atomic action refinement), relates processes of the two languages. Given a specification process p and an atomic action refinement ρ , the refined process ρ (p ) is proved to be an implementation of p . Moreover, a complete proof system for strong and weak equivalence are presented for both languages (and thus also for the operator of strong prefixing) and proved consistent with respect to refinement: if p and ρ are congruent processes of the specification language, then ρ (p ) and ρ (q ) are congruent, too. Show more

DOI: 10.3233/FI-1992-163-406

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 289-336, 1992

Authors: Paun, Gheorghe | Szijarto, Miklos | Vicolov, Sorina

Article Type: Research Article

Abstract: Union, homomorphic and inverse homomorphic representations of languages are obtained, starting from reduced languages introduced in earlier formal language approaches to parallel program schemes. The reduced-ness decidability is also investigated (it is decidable for regular and undecidable for linear languages).

DOI: 10.3233/FI-1992-163-407

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 337-347, 1992

Authors: Ehrenfeucht, Andrzej | Zawadowski, Marek W.

Article Type: Research Article

Abstract: We prove that every partial boolean algebra is isomorphic to a partial boolean algebra of sets. As a consequence we obtain finite axiomatization of the theory of partial boolean algebras.

DOI: 10.3233/FI-1992-163-408

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 349-353, 1992

Authors: Gasarch, William I. | Sitaraman, Ramesh K. | Smith, Carl H. | Velauthapillai, Mahendran

Article Type: Research Article

Abstract: Within the study of inductive inference a recurring theme has been to investigate the learning of programs that are not exactly correct. Previous work attempted to quantify the difference between the function to be learned and the one computed by the result of a learning process. In this paper we study a qualitative measure of approximate correctness of the result of attempting to learn a program for a given function. What we require is that the set of errors be somehow easy to describe.

DOI: 10.3233/FI-1992-163-409

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 355-370, 1992

Authors: Rauszer, Cecylia M.

Article Type: Research Article

Abstract: In the paper we consider a logical system called Decision Logic which may be used as a tool in the investigations of information systems. We provide two axiomatizations of that logic. One follows from the properties of information systems. The latter is in the style of proof theory. We prove the soundness and completeness theorems and show that both axiomatizations provide the same set of true formulae.

DOI: 10.3233/FI-1992-163-410

Citation: Fundamenta Informaticae, vol. 16, no. 3-4, pp. 371-382, 1992