Fundamenta Informaticae - Volume 112, issue 1

Authors: Penczek, Wojciech

Article Type: Other

DOI: 10.3233/FI-2011-574

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. v-v, 2011

Authors: Barbuti, Roberto | Levi, Francesca | Milazzo, Paolo | Scatena, Guido

Article Type: Research Article

Abstract: Maximally parallel semantics have been proposed for many formalisms as an alternative to the standard interleaving semantics for some modelling scenarios. Nevertheless, in the probabilistic setting an affirmed interpretation of maximal parallelism still lacks. We define a synchronous maximally parallel probabilistic semantics for multiset rewriting tailored to describe, simulate and verify biological systems evolving with maximally parallel steps. Each step of the proposed semantics is parallel as each reaction can happen multiple times, and it is maximal as it leaves no enabled reaction i.e. as many reactions as possible are executed. We define a maximally parallel probabilistic semantics in terms …of Discrete Time Markov Chain for systems described by stochastic multiset rewriting. We propose a simple, maximally parallel, model of Caenorhabditis elegans vulval development on which we show probabilistic simulations results. Show more

DOI: 10.3233/FI-2011-575

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 1-17, 2011

Authors: Belardinelli, Francesco | Jones, Andrew V. | Lomuscio, Alessio

Article Type: Research Article

Abstract: We introduce a novel automata-theoretic approach for the verification of multi-agent systems. We present epistemic alternating tree automata, an extension of alternating tree automata, and use them to represent specifications in the temporal-epistemic logic CTLK. We show that model checking a memory-less interpreted system against a CTLK property can be reduced to checking the language non-emptiness of the composition of two epistemic tree automata. We report on an experimental implementation and discuss preliminary results. We evaluate the effectiveness of the technique using two real-life scenarios: a gossip protocol and the train gate controller.

DOI: 10.3233/FI-2011-576

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 19-37, 2011

Authors: Czaja, Ludwik | Kudlek, Manfred

Article Type: Research Article

Abstract: We show that the results on analysis of net structures and transition graphs exhibited in [1] can be apllied also to generalized work flow net structures and related transition graphs.

DOI: 10.3233/FI-2011-577

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 39-45, 2011

Authors: Doliwa, Dariusz | Horzelski, Wojciech | Jarocki, Mariusz | Niewiadomski, Artur | Penczek, Wojciech | Półrola, Agata | Szreter, Maciej | Zbrzezny, Andrzej

Article Type: Research Article

Abstract: The paper presents a prototype toolset to planning by automatic composition of web services. The main idea consists in arranging the composition into two main phases: abstract and concrete one, as well as to handle fully declarative user queries. The first abstract stage aims at finding all the possible sequences of the types of the services that can potentially satisfy the user request. The result, referred to as an abstract plan, is used in the concrete planning phase, which substitutes the types of the services with their concrete instances registered in the system. This is obtained by translating the problem …of finding a composition of concrete services satisfying the user query into the reachability problem for (timed) automata with discrete data and parametric assignments, taking into account the concrete instances of services as well as the user query. Next, SAT-based parametric bounded model checking is used to obtaining the solutions in form of sequences of services invocations together with the example services' input values. Show more

DOI: 10.3233/FI-2011-578

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 47-71, 2011

Authors: Köhler-Bußmeier, Michael | Heitmann, Frank

Article Type: Research Article

Abstract: In this paper we study the complexity of the liveness problem for safe Elementary Object Nets (EOS). Object nets are Petri nets which have Petri nets as tokens. They are called elementary if the net system has a two levelled structure. The concept of safeness bounds the number of tokens which may reside on a place. PSPACE-hardness of the liveness problem for safe EOS directly follows from the related result for safe p/t nets. We then devise a polynomial space algorithm for this problem and indeed for every property that can be expressed in the temporal logic CTL.

DOI: 10.3233/FI-2011-579

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 73-87, 2011

Authors: Mellmann, Heinrich | Cotugno, Giuseppe

Article Type: Research Article

Abstract: The ability to grasp objects of different size and shape is one of the most important skills of a humanoid robot. There are a lot of different approaches tackling this problem; however, there is no general solution. The complexity and the skill of a possible grasping motion depend hardly on a particular robot. In this paper we analyze the kinematic and sensory grasping abilities of the humanoid robot Nao. Its kinematic constraints and hand's mechanical structure represent an interesting case of study due to lack of actuators for fingers and the limited computation power. After describing the platform and studying …its capabilities, we propose some simple controllers and we present a benchmark based on some experimental data. Show more

Keywords: motion generation, robot grasping, humanoid robot

DOI: 10.3233/FI-2011-580

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 89-101, 2011

Authors: Turek, Wojciech | Cetnarowicz, Krzysztof | Zaborowski, Wojciech

Article Type: Research Article

Abstract: Agent paradigm is becoming more and more popular in design of complex multi-robot systems. Similarities between features attributed to robots and agents lead to defining an agent as a single robot control program or even calling a robot an “embodied agents”. This approach can cause serious issues concerning scalability, extensibility and performance of large-scale multi-robot systems. In this paper a different approach to design and implementation of software systems managing mobile robots is presented. It is based on the logical separation of a hardware robot and a software agent. The paper focuses on improvements in system performance achieved by using …the approach. Three exemplary applications are described and experimental results are provided. Show more

Keywords: Software Agents, Mobile Robots

DOI: 10.3233/FI-2011-581

Citation: Fundamenta Informaticae, vol. 112, no. 1, pp. 103-117, 2011