Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Purchase individual online access for 1 year to this journal.
Price: EUR 410.00Impact Factor 2024: 0.4
Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:
- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.
Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.
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
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]