Fundamenta Informaticae - Volume 9, issue 1

Article Type: Other

DOI: 10.3233/FI-1986-9101

Citation: Fundamenta Informaticae, vol. 9, no. 1, pp. i-vi, 1986

Authors: Dayan, Ido | Harel, David

Article Type: Research Article

Abstract: The problem of transforming nondeterministic or concurrent programs involving fairness assumptions into fairness-free schedulers is considered. The availability of such transformations provides an indirect way of proving fair termination. Building upon a general tree-transformation result of Harel, and scheduler-yielding transformations of devised by several researchers, we provide a general way of finding such transformations for a very broad class of fairness criteria. In passing, we explicitly construct a scheduler for Pnueli’s rather elusive notion of extreme fairness. Our schedulers are really nondeterministic, and may be termed “cruel” since they leave choices to the program, but immediately thereafter cause it to …abort if it happens to make the wrong choice. Show more

DOI: 10.3233/FI-1986-9102

Citation: Fundamenta Informaticae, vol. 9, no. 1, pp. 1-11, 1986

Authors: Ehrig, Hartmut | Habel, Annegret | Rosen, Barry K.

Article Type: Research Article

Abstract: This paper provides a common framework to study transformations of structures ranging from all kinds of graphs to relational data structures. Transformations of structures can be used as derivations of graphs in the sense of graph grammars, as update of relations in the sense of relational data bases, or even as operations on data structures in the sense of abstract data types. The main aim of the paper is to construct parallel and concurrent transformations from given sequential ones and to study sequentializability properties of complex transformations. The main results are three fundamental theorems concerning parallelism, concurrency and decomposition of …transformations of structures. On one hand these results can be considered as a contribution to the study of con currency in graph grammars and on the other hand as a formal framework for consistent concurrent update of relational structures. Show more

DOI: 10.3233/FI-1986-9103

Citation: Fundamenta Informaticae, vol. 9, no. 1, pp. 13-49, 1986

Authors: Hoare, C.A.R. | Jifeng, He

Article Type: Research Article

Abstract: For, aside from the fact that the concepts occurring in this calculus possess an objective importance a nd are in these times almost indispensable in any scientific discussion, the calculus of relations has an intrinsic charm and beauty which makes it a source of intellectual delight to all who become acquainted with it. ALFRED TARSKI [10]

DOI: 10.3233/FI-1986-9104

Citation: Fundamenta Informaticae, vol. 9, no. 1, pp. 51-84, 1986

Authors: Tarjan, Robert Endre

Article Type: Research Article

Abstract: Many linear-time graph algorithms using depth-first search have been invented. We propose simplified versions of two such algorithms, for computing a bipolar orientation or st-numbering of an undirected graph and for finding all feedback vertices of a directed graph.

DOI: 10.3233/FI-1986-9105

Citation: Fundamenta Informaticae, vol. 9, no. 1, pp. 85-94, 1986

Authors: Tarlecki, Andrzej | Wirsing, Martin

Article Type: Research Article

DOI: 10.3233/FI-1986-9106

Citation: Fundamenta Informaticae, vol. 9, no. 1, pp. 95-125, 1986