Fundamenta Informaticae - Volume 143, issue 1-2

Authors: Czaja, Ludwik | Penczek, Wojciech | Stencel, Krzysztof

Article Type: Other

DOI: 10.3233/FI-2016-1299

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. v-vi, 2016

Authors: Bazan, Jan G. | Bazan-Socha, Stanislawa | Buregwa-Czuma, Sylwia | Dydo, Lukasz | Rzasa, Wojciech | Skowron, Andrzej

Article Type: Research Article

Abstract: This article introduces a new method of a decision tree construction. Such construction is performed using additional cuts applied for a verification of the cuts’ quality in tree nodes during the classification of objects. The presented approach allows us to exploit the additional knowledge represented in the attributes which could be eliminated using greedy methods. The paper includes the results of experiments performed on data sets from a biomedical database and machine learning repositories. In order to evaluate the presented method, we compared its performance with the classification results of a local discretization decision tree, well known from literature. Our …new method outperforms the existing method, which is also confirmed by statistical tests. Show more

Keywords: rough sets, discretization, concept approximation, classifiers

DOI: 10.3233/FI-2016-1300

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 1-18, 2016

Authors: Bazan, Jan G. | Szpyrka, Marcin | Szczur, Adam | Dydo, Lukasz | Wojtowicz, Hubert

Article Type: Research Article

Abstract: A new method of constructing classifiers from huge volume of temporal data is proposed in the paper. The novelty of introduced method finds expression in a multi-stage approach to build hierarchical classifiers that combines process mining, feature extraction based on temporal patterns and constructing classifiers based on a decision tree. Such an approach seems to be practical when dealing with huge volume of temporal data. As a proof of concept a system for packet-based network traffic anomaly detection was constructed, where anomalies are represented by spatio-temporal complex concepts and called by behavioral patterns. Hierarchical classifiers constructed with the new approach …turned out to be better than “flat” classifiers based directly on captured network traffic data. Show more

Keywords: classifiers, huge temporal data, temporal patterns, state graphs, behavioral patterns, LTL temporal logic

DOI: 10.3233/FI-2016-1301

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 19-34, 2016

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: The paper considers molecular programming in the abstract Tile Assembly Model, aTAM. Using simple constructions, an interpreter for the full Combinatory Logic, CL, is formally defined in aTAM. It provides an approach for sequential programming in aTAM, and produces a DNA molecular machine. This machine lives in a suitable solution and when receives a seed that linearly encodes a CL program and an input for the program, produces a grid which encodes a computation of the program on its input. The paper considers the construction cost and some alternative approaches. Finally, as a case study in distributed programming in aTAM, …the paper considers the consensus problem and shows how an aTAM program for it can be formally derived by using π-calculus. Show more

Keywords: DNA Tile self assembly, aTAM model, Combinatory Logic, π-calculus, Consensus problem

DOI: 10.3233/FI-2016-1302

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 35-49, 2016

Authors: Castiglioni, Valentina | Lanotte, Ruggero | Tini, Simone

Article Type: Research Article

Abstract: We study function elimination for Arithmetical Logics. We propose a method allowing substitution of functions occurring in a given formula with functions with less arity. We prove the correctness of the method and we use it to show the decidability of the satisfiability problem for two classes of formulas allowing linear and polynomial terms.

DOI: 10.3233/FI-2016-1303

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 51-71, 2016

Authors: Gruska, Damas P.

Article Type: Research Article

Abstract: A quantification of process’s security by differential privacy is defined and studied in the framework of probabilistic process algebras. The resulting (quantitative) security properties are investigated and compared with other (qualitative and quantitative) security notions.

Keywords: differential privacy, probabilistic process algebra, information flow, security, opacity, min-entropy

DOI: 10.3233/FI-2016-1304

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 73-87, 2016

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

Article Type: Research Article

Abstract: In this paper we study the complexity of the reachability problem HORNETS, an algebraic extension of object nets. Here we consider the restricted class of safe, elementary HORNETS. In previous work we established the lower bound, i.e. reachability requires at least exponential space. In another work we have shown we can simulate elementary HORNETS with elementary object nets EOS, where reachability is known to be PSpace-complete. Since this simulation leads to a double exponential increase in the size of the simulating EOS, we obtain that for HORNETS the reachability problem is solvable in double exponential space. In this …contribution we show that this kind of simulation is rather bad, since we show that exponential space is sufficient. Together with the known lower bound this shows that the upper is tight. Show more

Keywords: Hornets, nets-within-nets, object nets, reachability, safeness

DOI: 10.3233/FI-2016-1305

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 89-100, 2016

Authors: Lomazova, Irina A. | Popova-Zeugmann, Louchka

Article Type: Research Article

Abstract: In this paper we examine how it is possible to control Petri net behavior with the help of transition priorities. Controlling here means forcing a process to behave in a stable way by ascribing priorities to transitions and hence transforming a classic Petri net into a Priority Petri net. For Petri net models stability is often ensured by liveness and boundedness. These properties are crucial in many application areas, e.g. workflow modeling, embedded systems design, and bioinformatics. In this paper we study the problem of transforming a given live, but unbounded Petri net into a live and bounded one …by adding priority constraints. We specify necessary conditions for the solvability of this problem and present an algorithm for ascribing priorities to net transitions in such a way that the resulting net becomes bounded while staying live. Show more

DOI: 10.3233/FI-2016-1306

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 101-112, 2016

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: Combining CPDL (Propositional Dynamic Logic with Converse) and regular grammar logic results in an expressive modal logic denoted by CPDLreg . This logic covers TEAM LOG , a logical formalism used to express properties of agents’ cooperation in terms of beliefs, goals and intentions. It can also be used as a description logic for expressing terminological knowledge, in which both regular role inclusion axioms and CPDL-like role constructors are allowed. In this paper, we develop an expressive and tractable rule language called Horn-CPDLreg . As a special property, this rule language allows the concept constructor “universal restriction” to …appear on the left hand side of general concept inclusion axioms. We use a special semantics for Horn-CPDLreg that is based on pseudo-interpretations. It is called the constructive semantics and coincides with the traditional semantics when the concept constructor “universal restriction” is disallowed on the left hand side of concept inclusion axioms or when the language is used as an epistemic formalism and the accessibility relations are serial. We provide an algorithm with PTIME data complexity for checking whether a knowledge base in Horn-CPDLreg has a pseudo-model. This shows that the instance checking problem in Horn-CPDLreg with respect to the constructive semantics has PTIME data complexity. Show more

DOI: 10.3233/FI-2016-1307

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 113-139, 2016

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. It has been recently noticed that in the situation when the parser is to explore several alternatives one after another, no further alternatives need to be explored after the parser reached certain “cut point”. This fact can be used to save both processing time and storage. The subject of the paper is identification of cut points, which can also help in producing better diagnostics.

DOI: 10.3233/FI-2016-1308

Citation: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 141-149, 2016