Fundamenta Informaticae - Volume 6, issue 2

Article Type: Other

DOI: 10.3233/FI-1983-6201

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

Authors: Bertoni, Alberto | Mauri, Giancarlo | Miglioli, Pierangelo

Article Type: Research Article

Abstract: In this paper a comparative analysis of some algebraic and model-theoretic tools to specify abstract data types is presented: our aim is to show that, in order to capture a quite relevant feature such as the recursiveness of abstract data types, Model Theory works better than Category Theory. To do so, we analyze various notions such as “initiality”, “finality”, “monoinitiality”, “epifinality”, “weak monoinitiality” and “weak epifinality”, both from the point of view of “abstractness” and of “cardinality”, in a general model theoretical frame. For the second aspect, it is shown that only “initiality”, “monoinitiality”, “epifinality” and “weak epifinality” …allow us to select countable models (for theories with a countable language), a necessary condition to get recursive data types, while this is not the case for “finality” and “weak monoinitiality”. An extensive analysis is then devoted to the problem of the recursiveness of abstract data types: we provide a formal definition of recursiveness and show that it neither collapses, nor it is incompatible with the “abstractness” requirement. We also show that none of the above quoted categorial notions captures recursiveness. Finally, we consider our own definition of “abstract data type”, based on typically model-theoretic notions, and illustrate the sense according to which it captures recursiveness. Show more

Keywords: abstract data types, countability, recursiveness, homomorphisms, isomorphic embeddings

DOI: 10.3233/FI-1983-6202

Citation: Fundamenta Informaticae, vol. 6, no. 2, pp. 127-170, 1983

Authors: Sadowski, Zenon

Article Type: Research Article

Abstract: The paper contains an affirmative answer to the following question: Does nondeterministic sequential program equivalent with respect to the set of final valuations exist for every parallel program with semantics defined in paper[3]? It also includes an example of the construction of a nondeterministic sequential program equivalent with respect to the set of final valuations to the given parallel program.

Keywords: semantics of parallel program, semantics of nondeterministic program, FS-expressions, flowchart-schemes

DOI: 10.3233/FI-1983-6203

Citation: Fundamenta Informaticae, vol. 6, no. 2, pp. 171-183, 1983

Authors: Burkhard, Hans-Dieter

Article Type: Research Article

Abstract: Petri nets are considered where the firings are controlled by finite automata. The control may be distributed to different automata working over disjoint sets of transitions. To avoid deadlocks and conflicts for the whole system the distribution of control must be organized in an appropriate manner. The existence of deadlocks and conflicts is shown to be undecidable in general, but conflict resolving and deadlock free controls can be constructed for given nets.

Keywords: Petri nets, automata, control of concurrent systems, conflict, deadlock

DOI: 10.3233/FI-1983-6204

Citation: Fundamenta Informaticae, vol. 6, no. 2, pp. 185-215, 1983

Authors: Dańko, Wiktor

Article Type: Research Article

Abstract: In this paper we consider interpretability between algorithmic theories, i.e., formalized theories based on the algorithmic Logic (cf. [1,3]). We adopt the notion of interpretability proposed by Szczerba (cf. [7,8]). We show that some facts true in the case of interpretability of first order theories are also true in the case of interpretability of algorithmic theories. We give examples of hereditary and nonhereditary properties of interpretability of algorithmic theories.

Keywords: logics of programs, algorithmic logic, interpretability between formalized theories

DOI: 10.3233/FI-1983-6205

Citation: Fundamenta Informaticae, vol. 6, no. 2, pp. 217-233, 1983