Fundamenta Informaticae - Volume 157, issue 4

Authors: Czaja, Ludwik | Penczek, Wojciech | Schlingloff, Holger | Son, Nguyen Hung

Article Type: Other

DOI: 10.3233/FI-2018-1629

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. i-ii, 2018

Authors: Akhundov, Jafar | Tröger, Peter | Werner, Matthias

Article Type: Research Article

Abstract: Hybrid automata are a well-established modelling approach. The formalism is used in many real-time and control systems engineering projects, which makes model composition an increasingly relevant topic. A well-defined composition support allows concurrent engineering activities and the validation of larger systems. However, many existing publications seldom consider it or make unrealistic assumptions on the model design. The article discusses the common problems with hybrid automata composition and presents a new formalism, called linear time-invariant hybrid automata (LTI-HA), which targets specifically these issues. Our approach considers the superposition principle for flow functions, which makes it specifically useful for practical modelling …purposes in the spacecraft and control domain. We compare the approach to well-known related ideas, such as hybrid I/O automata. Several properties of composition, such as commutativity, are proven. Show more

Keywords: Hybrid Systems, Hybrid Automata, Composition, Linear Systems, Verification

DOI: 10.3233/FI-2018-1630

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 321-339, 2018

Authors: Barylska, Kamila | Erofeev, Evgeny | Koutny, Maciej | Mikulski, Łukasz | Piątkowski, Marcin

Article Type: Research Article

Abstract: Reversible computation deals with mechanisms for undoing the effects of actions executed by a dynamic system. This paper is concerned with reversibility in the context of Petri nets which are a general formal model of concurrent systems. A key construction we investigate amounts to adding ‘reverse’ versions of selected net transitions. Such a static modification can severely impact on the behaviour of the system, e.g., the problem of establishing whether the modified net has the same states as the original one is undecidable. We therefore concentrate on nets with finite state spaces and show, in particular, that every transition in …such nets can be reversed using a suitable set of new transitions. Show more

Keywords: Petri net, reversibility, reversible computation

DOI: 10.3233/FI-2018-1631

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 341-357, 2018

Authors: Czaja, Ludwik

Article Type: Research Article

Abstract: A new protocol using vectors of global timestamps for mutual exclusion in systems with Distributed Shared Memory (DSM) is described and some of its properties are proved.

DOI: 10.3233/FI-2018-1632

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 359-370, 2018

Authors: Jankowski, Andrzej | Skowron, Andrzej | Wasilewski, Piotr

Article Type: Research Article

Abstract: We discuss the rough set approach to approximation of vague concepts. There are already published several papers on rough sets and vague concepts staring from the seminal papers by Zdzisław Pawlak. However, only a few of them are discussing the relationships of rough sets with the sorites paradox. This paper contains a continuation of discussion on this issue.

Keywords: vagueness, vague concept, sorites paradox, (adaptive) rough set

DOI: 10.3233/FI-2018-1633

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 371-384, 2018

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: We provide the first algorithm with a polynomial time complexity, O ((m + n )2 n 2 ), for computing the largest bisimulation-based auto-comparison of a labeled graph in the setting with counting successors, where m is the number of edges and n is the number of vertices. This setting is like the case with graded modalities in modal logics and qualified number restrictions in description logics. Furthermore, by using the idea of Henzinger et al. for computing simulations, we give an efficient algorithm, with complexity O ((m + n )n ), for computing the largest …bisimulation-based auto-comparison and the directed similarity relation of a labeled graph in the setting without counting successors. We also adapt our former algorithm for computing the simulation pre-order of a labeled graph in the setting with counting successors. Show more

DOI: 10.3233/FI-2018-1634

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 385-401, 2018

Authors: Niewiadomski, Artur | Switalski, Piotr | Kowalczyk, Marcin | Penczek, Wojciech

Article Type: Research Article

Abstract: We present the web service composition system TripICS, which allows for an easy and user-friendly planning of visits to interesting cities and places around the world in combination with travels, arranged in the way satisfying the user’s requirements. TripICS is a specialization of the concrete planning of PlanICS viewed as a constrained optimization problem to the ontology containing services provided by hotels, airlines, railways, museums etc. The system finds an optimal plan by applying a modification of the most efficient concrete planner of PlanICS based on a combination of an SMT-solver with the algorithm GEO. The modification has been designed …in order to solve quickly multiple equality constraints. The efficiency of the new planning algorithm is proved by experimental results. Show more

Keywords: Web Service Composition, Concrete Planning, PlanICS, TripICS, SMT, Hybrid Algorithm, GEO

DOI: 10.3233/FI-2018-1635

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 403-425, 2018

Authors: Pelz, Elisabeth

Article Type: Research Article

Abstract: In this paper we use partial order semantics to express the truly concurrent behaviour of Interval-Timed Petri nets (ITPNs) in their most general setting, i.e. with autoconcurrency and zero duration, as studied with its standard maximal step semantics in [1]. First we introduce the notion of timed processes for ITPNs inductively. Then we investigate if the equivalence of inductive and axiomatic process semantics - true for classical Petri nets - could hold for ITPNs too. We will see that the notions of independence and immediate firing obligation seem to be antagonistic ones, and that local axioms, adequate to define processes …of classical Petri nets, are not sufficient to caracterize timed processes of ITPNs. We propose several original “global” axioms which reveal to be an effective solution. Thus we yield finally a full axiomatic definition of timed processes for ITPNs. Show more

DOI: 10.3233/FI-2018-1636

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 427-442, 2018

Authors: Rataj, Artur | Woźna-Szcześniak, Bożena

Article Type: Research Article

Abstract: We present different ways of an approximate extrapolation of an optimal policy of a small model to that of a large equivalent of the model, which itself is too large to find its exact policy directly using probabilistic model checking (PMC). In particular, we obtain a global optimal resolution of non-Cdeterminism in several small Markov Decision Processes (MDP) or its extensions like Stochastic Multi-player Games (SMG) using PMC. We then use that resolution to form a hypothesis about an analytic decision boundary representing a respective policy in an equivalent large MDP/SMG. The resulting hypothetical decision boundary is then statistically approximately …verified, if it is locally optimal and if it indeed represents a “good enough” policy. The verification either weakens or strengthens the hypothesis. The criterion of the optimality of the policy can be expressed in any modal logic that includes a version of the probabilistic operator P~p [·], and for which a PMC method exists. Show more

Keywords: probabilistic model checking, statistical model checking, non-determinism, optimal policy, extrapolation

DOI: 10.3233/FI-2018-1637

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 443-461, 2018

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. Its properties are useful in many applications, but it is not well understood as a language definition tool. In its appearance, PEG is almost identical to a grammar in the Extended Backus-Naur Form (EBNF), and one may expect it to define the same language. But, due to the limited backtracking, PEG may reject some strings defined by EBNF, which gives an impression of PEG being unpredictable. We note that for some grammars, the limited backtracking is “efficient”, in the sense that it exhausts all possibilities. A PEG with efficient …backtracking should therefore be easy to understand. There is no general algorithm to check if the grammar has efficient backtracking, but it can be often checked by inspection. The paper outlines an interactive tool to facilitate such inspection. Show more

DOI: 10.3233/FI-2018-1638

Citation: Fundamenta Informaticae, vol. 157, no. 4, pp. 463-475, 2018