Fundamenta Informaticae - Volume 60, issue 1-4

Authors: Burkhard, Hans-Dieter | Lindemann, Gabriela | Czaja, Ludwik | Suraj, Zbigniew

Article Type: Other

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. vii-viii, 2004

Authors: Mazurkiewicz, Antoni

Article Type: Research Article

Abstract: In general, a negotiation within a group of participants is a process, which starting with participants in some arbitrary (initial) states eventually come to an agreement with all participants being in the negotiated state. The formal method used for discussing the considered issue are local computations; in general, they consist in transforming states of whole structures by way of transforming states of some of their substructures. Negotiation procedures are local computations that act according to negotiation …protocols. The paper aims to discuss communication structures that admit negotiations limited to direct communications between at most two negotiating partners (bilateral negotiations). As a formal model of the communication structures graphs are used, with nodes representing participants of negotiations, edges the direct links between them, and a total (linear) ordering of nodes as the goal of negotiations; in our setup substructures subjected to transformations consist of two adjecent nodes only. There are known protocols that can solve particular problems; the question arises whether the same problems can be solved by local computations using substructures of size at most two. The present paper aims to offer an answer to this question. Show more

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 1-16, 2004

Authors: Mosses, Peter D.

Article Type: Research Article

Abstract: Structural Operational Semantics (SOS) allows transitions to be labelled. This is fully exploited in SOS descriptions of concurrent systems, but usually not at all in conventional descriptions of sequential programming languages. This paper shows how the use of labels can provide significantly simpler and more modular descriptions of programming languages. However, the full power of labels is obtained only when the set of labels is made into a category, as in the recently-proposed MSOS variant of …SOS. Show more

Keywords: Structural operational semantics, SOS, modularity, MSOS, natural semantics

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 17-31, 2004

Authors: Pawlak, Zdzisław

Article Type: Research Article

Abstract: We proposed in this paper to use some ideas of Jan Łukasiewicz, concerning independence of logical formulas, to study dependencies in databases.

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 33-39, 2004

Authors: Ambroszkiewicz, Stanisław

Article Type: Research Article

Abstract: There are two general approaches to integration of heterogeneous applications. The first one corresponds to business-to-business point of view, whereas the second one to the client's point of view. The first one is based on the assumption that applications are composed, orchestrated, or choreographed in order to create sophisticated business processes, whereas the second one assumes that applications are composed (typically on the fly) in order to realize clients' requests. In this work the client's point …of view is taken and a new experimental technology for service description and composition in open and distributed environment is proposed. The technology consists of description language called Entish, and composition protocol called entish 1.0. Show more

Keywords: service-oriented architecture, service description and composition, software agents

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 41-66, 2004

Authors: Barbuti, Roberto | Cataudella, Stefano | Tesei, Luca

Article Type: Research Article

Abstract: In this paper we investigate the use of abstract interpretation techniques for statically preventing race conditions. To this purpose we enrich the concurrent object calculus concζ by annotating terms with the set of "locks" owned at any time. We use an abstract form of the object calculus to check the absence of race conditions. We show that abstract interpretation is more flexible than type analyses, and it allows to certify as "race free" a larger class …of programs. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 67-79, 2004

Authors: Bernardeschi, Cinzia | De Francesco, Nicoletta | Lettieri, Giuseppe

Article Type: Research Article

Abstract: This paper presents a technique for verifying secure information flow in concurrent programs consisting of a number of independently executing sequential processes with private memory. Communications between processes are synchronous. Moreover, processes are open systems that can accept inputs from the environment and produce outputs towards the environment. The technique is based on an abstract interpretation. First we define a concrete instrumented …semantics where each value is annotated with the security level of the information on which it depends. Then we define an abstract semantics of the language that abstracts from actual data and maintains only the annotations on the security level. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 81-98, 2004

Authors: Doroshenko, Analoliy | Tseitlin, Georgy

Article Type: Research Article

Abstract: An approach based on algebraic treatment of programs and advanced transition system operational semantics is described for asynchronous communication of parallel distributed/shared memory programs. The approach aimes at efficient synchronization and combines compile- and run-time data flow analysis to improves computation and communication overlapping. A number of semantic models of data exchanges of increasing power for asynchronous communication in distributed environment are constructed. Two programming abstractions, exchange environs and coordination expressions, aimed …to reduce communication and synchronization overhead are derived from the theory. The program models constructed give more theoretical insight into the nature of parallelism of computation and communication and have immediate practical influence on parallel programming. Particularly automatic resolution of some classes of communication deadlocks are allowed and enhancement of data parallel par Show more

Keywords: concurrency of computation and communication, program abstractions, coordination expressions

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 99-111, 2004

Authors: Farwer, Berndt | Köhler, Michael

Article Type: Research Article

Abstract: The Petri-net-based formalism of mobile object-net systems (Mons) is used to model concurrent systems with dynamically changing environments, such as mobile objects. The tokens in Mons are themselves Petri nets, which gives the formalism an additional (vertical) dimension of nesting. Traditional Petri nets have essentially a horizontal structure, given by the fact that markings are multisets. The question arises, whether Mons can be regarded as a canonical extension of such Petri nets. Due to the nested …nature of Mons, the answer is not obvious. We first give the formal definition of Mons and then prove some properties of the formalism, showing that, with respect to interleaving semantics (i.e. firing sequences), Mons can indeed be viewed as a canonical extension of traditional Petri nets. We then define Mons processes, also as a canonical extension of standard Petri net processes. Show more

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 113-129, 2004

Authors: Farwer, Berndt | Kudlek, Manfred

Article Type: Research Article

Abstract: The present paper continues work from [7]. One goal of this work is to find a class of (object) Petri nets of lesser power than Turing machines, such that there exists a universal Petri net within that class. Another goal is to surpass the restricted synchronisation of transitions in object and system nets in the case of value semantics. Finally, an encoding of the proposed class of object Petri nets into linear logic Petri nets (LLPNs) is given, which …directly leads to a specification that can be model-checked by existing tools. Show more

Keywords: universal Petri net, universal machine, object Petri net, higher-order Petri net, synchronisation, value semantics

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 131-142, 2004