Fundamenta Informaticae - Volume 102, issue 1

Authors: Penczek, Wojciech

Article Type: Other

DOI: 10.3233/FI-2010-292

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. i-i, 2010

Authors: Peter Bachmann, Jörg | Popova-Zeugmann, Louchka

Article Type: Research Article

Abstract: In this paper we consider a class of Time Petri nets defined by structural restrictions. Each Time Petri net which belongs to this class has the property that their liveness behaviour does not depend on the time. Therefore, the Time Petri net is live when its skeleton is live.

DOI: 10.3233/FI-2010-293

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 1-17, 2010

Authors: Barbuti, Roberto | Maggiolo-Schettini, Andrea | Milazzo, Paolo | Gruska, Damas P.

Article Type: Research Article

Abstract: A formal model for diagnostics of biological systems modelled as P systems is presented. We assume the presence of some biologically motivated changes (frequently pathological) in the systems behavior and investigate when these changes could be diagnosed by an external observer by exploiting some techniques originally developed for reasoning on system security.

DOI: 10.3233/FI-2010-294

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 19-34, 2010

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

Article Type: Research Article

Abstract: The aim of the paper is to propose how to enrich a formal model of persuasion with a specification for actions which are typical for persuasion process. First, since these actions are verbal, they influence a receiver but do not change the agent’s environment. In a formal framework, we represent them as actions that change not the particular state of a model, but the whole model. Second, effects of those actions depend on how much the receiver trusts the persuader. To formally model this phenomenon, we use a trust function. Finally, we want to represent uncertainty in terms of probability. …Thus far, our model did not allow to express those properties of the persuasion process. Therefore, in this paper we extend Multimodal Logic of Actions and Graded Beliefs (AGn ) with Probabilistic Dynamic Epistemic Logic (PDEL) and elements of Reputation Management framework (RM). Incorporation of PDEL into the model of persuasion requires some modifications of PDEL. Such extended model is then used to enrich Perseus – our software tool that enables to examine persuasive multi-agent systems. New components of the tool allow us to execute parametric verification of the different properties related to updating probabilistic beliefs in persuasion. Show more

DOI: 10.3233/FI-2010-295

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 35-48, 2010

Authors: Burkhard, Hans-Dieter

Article Type: Research Article

Abstract: Robots and agents are both autonomously interacting with their environment. It is even argued that robots can be regarded as embodied agents. This paper discusses the use of Agent Oriented Techniques for controlling robots, their benefits and their limitations. Basic skills need much more emphasis for robots than related skills of agents. Algorithms for perception in the real world are a key problem for robot programming with many (still unsolved) challenges. More deliberative tasks like planning can benefit from techniques developed for agents. Since real environments are highly dynamic, classical planning techniques are not flexible enough, but there exist more …sophisticated techniques for agents which are useful for robotics as well. Show more

Keywords: Agent Technics, Cognitive Robotics

DOI: 10.3233/FI-2010-296

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 49-62, 2010

Authors: Gruska, Damas P.

Article Type: Research Article

Abstract: A general framework for defining security properties is presented. It allows us to model many traditional security properties as well as to define new ones. The framework is based on process algebras contexts and processes relations. By appropriate choice of both of them we can model also probabilistic and quantified security properties.

Keywords: information flow, opacity, surprisal, uncertainty, security, quantified information flow

DOI: 10.3233/FI-2010-297

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 63-76, 2010

Authors: Lomuscio, Alessio | Strulo, Ben | Walker, Nigel G. | Wu, Peng

Article Type: Research Article

Abstract: Model checking has been widely applied to the verification of network protocols. Alternatively, optimisation based approaches have been proposed to reason about the large scale dynamics of networks, particularly with regard to congestion and rate control protocols such as TCP. This paper intends to provide a first bridge and explore synergies between these two approaches. We consider a series of discrete approximations to the optimisation based congestion control algorithms. Then we use branching time temporal logic to specify formally the convergence criteria for the system dynamics and present results from implementing these algorithms on a state-of-the-art model checker. We report …on our experiences in using the abstraction of model checking to capture features of the continuous dynamics typical of optimisation based approaches. Show more

Keywords: Model Checking, Distributed Optimisation, Congestion Control, Convergence

DOI: 10.3233/FI-2010-298

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 77-96, 2010

Authors: Anh Nguyen, Linh | Szałas, Andrzej

Article Type: Research Article

Abstract: We reformulate Pratt’s tableau decision procedure of checking satisfiability of a set of formulas in PDL. Our formulation is simpler and its implementation is more direct. Extending the method we give the first ExpTime (optimal) tableau decision procedure not based on transformation for checking consistency of an ABox w.r.t. a TBox in PDL (here, PDL is treated as a description logic). We also prove a new result that the data complexity of the instance checking problem in PDL is coNP-complete.

DOI: 10.3233/FI-2010-299

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 97-113, 2010

Authors: Srebrny, Marian | Stepień, Lidia

Article Type: Research Article

Abstract: In this paper we pursue the propositional calculus and the SATisfiability solvers as a powerful declarative programming environment that makes it possible to create and run the propositional declarative programs for computational tasks in various areas of mathematics. We report some experimental results on our application of the propositional SATisfiability environment to computing some simple orthogonal matrices and the orders of some orthogonal groups. Some encouraging (and not very encouraging) experiments are reported for the proposed propositional search procedures using off-the-shelf general-purpose SAT solvers. Our new software toolkit SAT4Alg is announced.

Keywords: satisfiability, linear algebra, orthogonal matrices, orthogonal groups, declarative programming

DOI: 10.3233/FI-2010-300

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 115-127, 2010

Authors: Virbitskaite, Irina | Gribovskaya, Natalya | Best, Eike

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 how several categorical (open maps, path-bisimilarity and coalgebraic) approaches to an abstract characterization of bisimulation relate to each other and to the numerous suggested behavioural equivalences of linear time – branching time spectrum, in the setting of timed transition systems.

DOI: 10.3233/FI-2010-301

Citation: Fundamenta Informaticae, vol. 102, no. 1, pp. 129-143, 2010