Fundamenta Informaticae - Volume 12, issue 4

Article Type: Other

DOI: 10.3233/FI-1989-12401

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. i-vii, 1989

Authors: Benson, David B.

Article Type: Research Article

Abstract: A categorical bimonoid consists of a monoid and a comonoid which act homomorphically on one another. In applications bimonoids are typically called bialgebras or Hopf algebras. The definitions are given at a level suitable to computer science applications and examples are included. The elements of the theory of graded bialgebras are developed and we provide a universal recursion theorem for morphisms between algebras and between coalgebras. With this theory we explicate refinements of concurrent programs and give a treatment of traces. The concluding section characterizes all coalgebras which interact with the match algebra to form a bialgebra and characterizes all …algebras which interact with the fork (diagonal) coalgebra to form a bialgebra. Show more

DOI: 10.3233/FI-1989-12402

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 427-486, 1989

Authors: Kowalczyk, Wojciech

Article Type: Research Article

DOI: 10.3233/FI-1989-12403

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 487-496, 1989

Authors: Kowalczyk, Wojciech | Niwinski, Damian | Tiuryn, Jerzy

Article Type: Research Article

DOI: 10.3233/FI-1989-12404

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 497-505, 1989

Authors: Moser, Louise E.

Article Type: Research Article

Abstract: A nonmonotonic logic of belief based on a combined monotonic logic of knowledge and belief is presented. Unlike previous nonmonotonic logics of belief, this logic contains an unless operator by means of which preference for beliefs and refutation of those beliefs can be expressed, thereby providing explicit representation of nonmonotonicity. A decision procedure based on Kripke structures for deciding validity of formulas in the logic is described and proved correct.

DOI: 10.3233/FI-1989-12405

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 507-523, 1989

Authors: Böhm, C. | Dezani-Ciancaglini, M.

Article Type: Research Article

DOI: 10.3233/FI-1989-12406

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 525-539, 1989

Authors: Pettorossi, Alberto | Skowron, Andrzej

Article Type: Research Article

Abstract: In a previous paper of ours [Pettorossi-Skowron 87] we have introduced the higher order generalization strategy (also called lambda abstraction strategy ) and we have indicated through some examples its use for the automatic derivation of programs. Here we study that strategy in more detail and we analyze its capabilities for obtaining highly efficient programs, considering also some cases in which other known strategies for program development do not work.

DOI: 10.3233/FI-1989-12407

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 541-561, 1989

Authors: Mäkinen, Erkki

Article Type: Research Article

Abstract: Eades and Wormald have shown that a bipartite graph drawn by the median heuristic has at most three times the number of edge crossing in the corresponding optimal drawing. In this paper we show that the bound of Eades and Wormald can be sharpened.

Keywords: bipartite graph, graph drawing, median heuristic, average heuristic, edge crossing

DOI: 10.3233/FI-1989-12408

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 563-569, 1989

Authors: Fachini, E. | Maggiolo Schettini, A. | Resta, G. | Sangiorgi, D.

Article Type: Research Article

Abstract: We prove that the classes of languages accepted by systolic automata over t-ary trees (t-STA) are always either equal or incomparable if one varies t. We introduce systolic tree automata with base (T(b)-STA), a subclass of STA with interesting properties of modularity, and we give a necessary and sufficient condition for the equivalence between a T(b)-STA and a t-STA, for a given base b. Finally, we show that the stability problem for T(b)-ST A is decidible.

DOI: 10.3233/FI-1989-12409

Citation: Fundamenta Informaticae, vol. 12, no. 4, pp. 571-585, 1989