Fundamenta Informaticae - Volume 93, issue 1-3

Article Type: Other

DOI: 10.3233/FI-2009-0083

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. i-i, 2009

Authors: Balicki, Krzysztof | Szpyrka, Marcin

Article Type: Research Article

Abstract: The paper presents a formal definition of XCCS – a graphical extension of CCS process calculus. The aim of this extension is to supply graphical means for creating models and thus to eliminate problems typical for modelling in textual manner inherent to CCS process algebra. XCCS diagrams consist of two layers, a graphical one that represents the structure of a modelled system and algebraic one that describes behaviour of individual agents. The graphical layer takes the …form of a directed graph, while the algebraic one is a set of sequences of algebraic equations similar to those in the CCS calculus. The formal definition presented in the paper deals with both parts of such models. At the end of the paper we define the Synchronization Relation and present the Basic Conversion Algorithm that converts XCCS diagrams into CCS scripts. Show more

Keywords: XCCS process algebra, formal definition, synchronization relation, Basic Conversion Algorithm

DOI: 10.3233/FI-2009-0084

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 1-15, 2009

Authors: Barbuti, Roberto | Maggiolo-Schettini, Andrea | Milazzo, Paolo | Tini, Simone

Article Type: Research Article

Abstract: P Systems are computing devices inspired by the structure and the functioning of a living cell. A P System consists of a hierarchy of membranes, each of them containing a multiset of objects, a set of evolution rules, and possibly other membranes. Evolution rules are applied to the objects of the same membrane with maximal parallelism. In this paper we present an extension of P Systems, called P Systems with Membrane Channels (PMC Systems), in which …membranes are enriched with channels and objects can pass through a membrane only if there are channels on the membrane that enable such a passage. We show that PMC Systems are universal even if only the simplest form of evolution rules is considered, and we give two application examples. Show more

DOI: 10.3233/FI-2009-0085

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 17-31, 2009

Authors: Barylska, Kamila | Ochma´nski, Edward

Article Type: Research Article

Abstract: The notion of persistency, based on the rule "no action can disable another one" is one of the classical notions in concurrency theory. We propose two ways of generalization of this notion: the first is "no action can kill another one" and the second "no action can kill another enabled one". We study the three notions in the context of place/transition nets, the fundamental class of Petri nets. We prove that the …three classes of persistency form an increased strict hierarchy. The final section of the paper deals with decision problems about persistency. We show that the set reachability problem is decidable for rational convex sets, and using this result we prove that all kinds of persistency are decidable in the class place/transition nets. Show more

DOI: 10.3233/FI-2009-0086

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 33-43, 2009

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: M_parameters extend Java by allowing methods to have methods as parameters. [8] furnishes a semantics of m parameters and applications in OO programming. In this paper, we present an implementation of the extended language based on program preprocessing. We also discuss the integration of the extended programs with ordinary Java programs, and hence Java API. Furthermore, mc parameters are defined: they are a variant of m parameters for which the class hierarchy of the method passed …as parameter must be provided in the formal and actual parameter. Semantics for mc parameters is given but, in this case, an implementation with callbacks [20] is proposed. Eventually, we discuss how mc_parameters deal with overloaded methods. Show more

DOI: 10.3233/FI-2009-0087

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 45-64, 2009

Authors: Budzyńska, Katarzyna | Kacprzak, Magdalena | Rembelski, Paweł

Article Type: Research Article

Abstract: The aim of the paper is to present the software tool Perseus and show how it can be used to examine multi-agent systems where the ability to persuade is specified. Especially we want to study the issues such as: what arguments individuals use to successfully convince others, what type of a persuader guarantees a victory etc. This work describes implementation of the tool and discusses what questions about persuasion process Perseus can answer and how it …is done. Show more

DOI: 10.3233/FI-2009-0088

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 65-79, 2009

Authors: Bulling, Nils | Jamroga, Wojciech

Article Type: Research Article

Abstract: Alternating-time Temporal Logic (ATL) is probably themost influential logic of strategic ability that has emerged in recent years. The idea of ATL is centered around cooperation modalities: ≪A≫γ is satisfied if the group A of agents has a collective strategy to enforce temporal property γ against the worst possible response from the other agents. So, the semantics of ATL shares the "all-or-nothing" attitude of many logical approaches to computation. Such …an assumption seems appropriate in some application areas (life-critical systems, security protocols, expensive ventures like space missions). In many cases, however, one might be satisfied if the goal is achieved with reasonable likelihood. In this paper, we try to soften the rigorous notion of success that underpins ATL. Show more

DOI: 10.3233/FI-2009-0089

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 81-96, 2009

Authors: Czaja, Ludwik | Kudlek, Manfred

Article Type: Research Article

Abstract: We investigate relations between transition graphs and net structures. Whereas for a given net structure there always exists a reachability graph, the inverse problem to find a net structure for a given transition graph is not solvable in general. We present sufficient and necessary conditions for several classes of transition graphs such as general, pseudo-bounded, bounded and elementary transition graphs, corresponding to general and (pseudo-)bounded P/T nets or C/E nets. We also give maximal and …minimal solutions within an algebraic structure of net structures. The entire investigation is formulated in the framework of multiset theory. Show more

DOI: 10.3233/FI-2009-0090

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 97-110, 2009

Authors: Doroshenko, Anatoliy | Yatsenko, Olena

Article Type: Research Article

Abstract: An approach to formalized development of parallel programs using ontologies and algebra- algorithmic facilities is proposed. Ontology gives opportunity to describe the skeleton of the program representing main objects in the given subject domain, i.e. data, functions to process data and relations between functions. Once the skeleton of the program has been built, further development can be done in automated manner with the Integrated toolkit for Design and Synthesis (IDS) developed by the authors, which is …based on using algorithmic algebras facilities. The application of the approach is illustrated with an example of developing parallel MPI program in the subject domain of sorting algorithms. Show more

Keywords: ontology, algebra of algorithms, designing and synthesis of programs, parallel programs

DOI: 10.3233/FI-2009-0091

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 111-125, 2009

Authors: Gribovskaya, Natalya | Virbitskaite, Irina

Article Type: Research Article

Abstract: Timed transition systems are a widely studied model for real-time systems. The intention of the paper is to show the applicability of the general categorical framework of openmaps in order to prove that timed delay equivalence is indeed an equivalence relation in the setting of timed transition systems with invariants. In particular, we define a category of the model under consideration and an accompanying (sub)category of observations to which the corresponding notion of open maps is …developed. We then use the open maps framework to obtain an abstract equivalence relation which is established to coincide with timed delay bisimulation. Show more

Keywords: timed transition systems, timed delay equivalence, category theory, open maps

DOI: 10.3233/FI-2009-0092

Citation: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 127-142, 2009