Fundamenta Informaticae - Volume 13, issue 3

Article Type: Other

DOI: 10.3233/FI-1990-13301

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. i-viii, 1990

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: Theory of reducing operators elaborated for pure generalized grammars in [5] is transferred to normed generalized grammars. There exists a reducing operator ρ such that. for any normed generalized grammar G the normed generalized grammars G , ρ (G ) generate the same languages; furthemore: ρ (G) is a normed grammar if and only if there exists a normed grammar G ′ such that G and G ′ generate the same language and G ′ is in a certain …sense smaller than or equal to G . The reducing operator ρ is used to characterize the so called harmonic languages. Show more

Keywords: normed generalized grammar, permitting triple defined by means of derivatives, language grammatizable by means of derivatives, language weakly grammatizable by means of derivatives, harmonic grammar, harmonic language, reducing operator for generalized grammars

DOI: 10.3233/FI-1990-13302

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 237-244, 1990

Authors: Skowron, Andrzej

Article Type: Research Article

Abstract: The aim of the paper is to show some connections between the rough sets theory and the Dempser-Shafer approach. We prove that for every Pawlak’s approximation space there exists a Dempster-Shafer space with the qualities of the lower and upper approximations of sets in the approximation space equal to the credibility and plausibility of sets in the Dempster-Shafer space, respectively. Analogous connections hold between approximation spaces generated by the decision tables and Dempster-Shafer spaces, namely for every decision table space there exists a Dempster-Shafer space such that the qualities of the lower and upper approximations (with respect to …the condition attributes) of sets definable in the decision table by condition and decision attributes coincide with the credibility and plausibility of sets in the Dempster-Shafer space, respectively. A combination rule in approximation spaces analogous to the combination rule used in the Dempster approach is derived. Show more

DOI: 10.3233/FI-1990-13303

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 245-262, 1990

Authors: Romanowska, Anna B. | Smith, Jonathan D.H.

Article Type: Research Article

Abstract: A significant contribution to the analysis of certain aspects of the communicating processes model was made by D. Benson’s proposal to view incompletely specified nondeterministic processes as modules over certain semirings, and dually as comodules over corresponding coalgebras. The effectiveness of the proposal in treating the synthesis of such processes under mutual communication depended on the good behaviour of these algebraic systems with respect to tensor products. The aim of the paper is to draw attension to the algebraic theory underlying Benson’s proposal, the theory of entropic algebras. Working with entropic algebras guarantees that tensor products are sufficiently well-behaved to …make Benson’s theory work. Show more

DOI: 10.3233/FI-1990-13304

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 263-274, 1990

Authors: Keesmaat, N.W. | Kleijn, H.C.M. | Rozenberg, G.

Article Type: Research Article

Abstract: A model of concurrent systems, called Vector Controlled Concurrent Systems, is introduced. It generalizes the vector synchronization mechanism used in path expressions (COSY). In this first part of the paper, which consists of two parts, the basic model is introduced and motivated, and then a distinction is made between static and dynamic submodels.

DOI: 10.3233/FI-1990-13305

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 275-316, 1990

Authors: Hirani, Anil | Subrahmanian, V.S.

Article Type: Research Article

Abstract: Given a logic program P , the operator T P associated with P is closely related to the intended meaning of P . Given a first order language L that is generated by finitely many non-logical symbols, our aim is to study the algebraic properties of the set {T P |P is a general logic program in language L } with certain operators on it. For the operators defined in this paper the resulting algebraic structure is a bounded distributive lattice. Our study extends (to the case of general logic programs), the work of …Mancarella and Pedreschi who initiated a study of the algebraic properties of the space of pure logic programs. We study the algebraic properties of this set and identify the ideals and zero divisors. In addition, we prove that our algebra satisfies various non-extensibility conditions. Show more

DOI: 10.3233/FI-1990-13306

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 317-332, 1990

Authors: Stachniak, Zbigniew | O’Hearn, Peter

Article Type: Research Article

Abstract: In this paper the notion of a resolution counterpart of a propositional logic is introduced and studied. This notion is based on a generalization of the resolution rule of J.A. Robinson. It is shown that for every strongly finite logic a refutationally complete nonclausal resolution proof system can be constructed and that the completeness of such systems is preserved with respect to the polarity and set of support strategies.

DOI: 10.3233/FI-1990-13307

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 333-351, 1990

Authors: Darondeau, Philippe | Gamatie, Boubakar

Article Type: Research Article

Abstract: We present a denotational model for CCS, accounting for finite as well as infinite behaviours. The meanings of programs are combinations of ready sets and infinitary languages. The model is shown fully abstract w.r.t. the equivalence u ∼ v if L(u,t)=L(v,t) for any testing program t, where L(p,q) is the set of totally ordered traces of communications between programs p and q set in parallel.

DOI: 10.3233/FI-1990-13308

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 353-386, 1990

Authors: Kleine Büning, Hans | Löwen, Ulrich

Article Type: Research Article

Abstract: We investigate the average complexity of various classes of binary propositional Prolog programs. We consider classes of tree-like programs introducing a concept of unary and binary edges in a tree to manage situations where a consequence A ← B of a Prolog program can be derived in several ways. We establish exponential lower bounds for the average complexity of tree-like Prolog programs having no facts and we have polynomial upper bounds for various classes of tree-like Prolog programs with facts. These results should be considered as a first step towards the average complexity of propositional Prolog programs.

DOI: 10.3233/FI-1990-13309

Citation: Fundamenta Informaticae, vol. 13, no. 3, pp. 387-399, 1990