Fundamenta Informaticae - Volume 128, issue 1-2

Authors: Czaja, Ludwik

Article Type: Other

DOI: 10.3233/FI-2013-928

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. v-v, 2013

Authors: Azad, Mohammad | Chikalov, Igor | Moshkov, Mikhail | Zielosko, Beata

Article Type: Research Article

Abstract: In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be …useful from the point of view of knowledge representation and algorithm construction. Show more

Keywords: Decision table with many-valued decisions, decision tree, greedy algorithm

DOI: 10.3233/FI-2013-929

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 1-15, 2013

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: The last proposal for Java closures, as emerged in JSR 000335, is mainly innovative in: (1) Use of nominal types, SAM types, for closures; (2) Introduction of target types and compatibility for a contextual typing of closures; (3) Need for a type inference that reconstructs the omitted type annotations of closures and closure arguments. The paper provides a sound and complete type system, with nominal types, for such a type inference and discusses role and formalization of targeting and of compatibility in the designed inference process.

DOI: 10.3233/FI-2013-930

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 17-33, 2013

Authors: Czaja, Ludwik

Article Type: Research Article

DOI: 10.3233/FI-2013-931

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 35-45, 2013

Authors: Dąbrowski, Robert | Timoszuk, Grzegorz | Stencel, Krzysztof

Article Type: Research Article

Abstract: The software architecture is typically defined as the fundamental organization of the system embodied in its components, their relationships to one another and to the system's environment. It also encompases principles governing the system's design and evolution. In order to manage the architecture of a large software system the architect needs a holistic model that supports continuous integration and verification for all system artifacts. In earlier papers we proposed a unified graph-based approach to the problem of managing knowledge about the architecture of a software system. In this paper we demonstrate that this approach facilitates convenient and efficient project measurement. …First, we show how existing software metrics can be translated into our model in a way that is independent of the programming language. Second, we introduce new metrics that cross the programming language boundaries and are easily implementable using our approach. We conclude by demonstrating how the new model can be implemented using existing tools. In particular, graph databases are a convenient implementation of an architectural repository. Graph query languages and graph algorithms are an effective way to define metrics and specialized graph views. Show more

Keywords: software measurement, architectural knowledge, software architecture

DOI: 10.3233/FI-2013-932

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 47-63, 2013

Authors: Grabowski, Adam

Article Type: Research Article

Abstract: The computer certification of rough sets (the translation in a way understandable by machines) seems to be far beyond the test phase. To assure the feasibility of the approach, we try to encode selected problems within rough set theory and as the testbed of already developed foundations – and in the same time as a payoff of the established framework – we shed some new light on the well-known question of generalization of rough sets and the axiomatization of approximation operators in terms of (various types of) binary relations. We show how much the human work can be enhanced with …the use of automatic tools, without loosing too much time for the translation. Although the syntax is understandable by the computer, it offers relative flexibility and expressive power of the formal language. Show more

Keywords: rough sets, generalized rough approximations, formalization of mathematics

DOI: 10.3233/FI-2013-933

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 65-79, 2013

Authors: Gruska, Damas P.

Article Type: Research Article

Abstract: Process testing as a way to obtain information on confidential data is investigated. Our working formalism is based on an appropriate (probabilistic) process algebra and (probabilistic) testing. We define testing noninterference as well as sets of private actions which execution is guaranteed by a given test and sets of actions which execution could be excluded by a given test. Moreover, we relate obtained information to a size of the test.

Keywords: probabilistic process algebras, information flow, security

DOI: 10.3233/FI-2013-934

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 81-95, 2013

Authors: Köhler-Bußmeier, Michael

Article Type: Research Article

Abstract: In this paper we develop a negotiation and contracting framework for inter-organisational workflows. The overall aim is to compute a group-plan from a given set of individual plans, where plans are formulated in the context of a given inter-organisational workflow between the agents. A general problem is that the individual plans are not consistent, i.e. the intersection of all individual plans does not contain a complete process, which leads from the initial state of the workflow to its final state. Therefore, negotiation is needed to obtain a compromise. In this paper we develop a generic negotiation protocol and use branching …processes as the elementary data structure. The generic protocol is adapted within the specifics of our SONAR-framework. SONAR is a specification framework that defines the organisational structure of multi-agent systems. SONAR has a formal notion of teams and team-formation which is used here to instantiate the strategy parameters. Show more

Keywords: branching processes, inter-organisational workflow, negotiation protocol, partial plans, Petri net, SONAR, teamwork, unfoldings

DOI: 10.3233/FI-2013-935

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 97-111, 2013

Authors: Kudlek, Manfred | Flick, Nils Erik

Article Type: Research Article

Abstract: We present basic structures, definitions, normal forms, and a hierarchy of languages based on catenation, shuffle and their iterations, defined by algebraic closures or least fixed point solutions to systems of equations.

DOI: 10.3233/FI-2013-936

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 113-128, 2013

Authors: Lomazova, Irina A. | Romanov, Ivan V.

Article Type: Research Article

Abstract: In this work we consider modeling of services with workflow modules, which form a Petri net subclass. The service compatibility problem is to answer the question, whether two services fit together, i.e. whether the composed system is correct. We study complementarity of resources, produced/consumed by two services—a necessary condition for the service compatibility. Resources, which are produced/consumed by a service, are represented as a multiset language. We define an algebra of multiset languages and present algorithms for checking conformance of resources for two given well-structured workflow modules.

DOI: 10.3233/FI-2013-937

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 129-141, 2013

Authors: Pancerz, Krzysztof | Lewicki, Arkadiusz | Tadeusiewicz, Ryszard | Warchoł, Jan

Article Type: Research Article

Abstract: In the paper, we focus on ant-based clustering time series data represented by means of the so-called delta episode information systems. A clustering process is made on the basis of delta representation of time series, i.e., we are interested in characters of changes between two consecutive data points in time series instead of original data points. Most algorithms use similarity measures to compare time series. In the paper, we propose to use a measure based on temporal rough set flow graphs. This measure has a probabilistic character and it is considered in terms of the Decision Theoretic Rough Set (DTRS) …model. To perform ant-based clustering, the algorithm based on the versions proposed by J. Deneubourg, E. Lumer and B. Faieta as well as J. Handl et al. is used. Show more

DOI: 10.3233/FI-2013-938

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 143-158, 2013

Authors: Peters, James F. | Skowron, Andrzej | Stepaniuk, Jaroslaw

Article Type: Research Article

Abstract: The problem considered in this paper is how to describe and compare visual objects. The solution to this problem stems from a consideration of nearness relations in two different forms of Efremovič proximity spaces. In this paper, the visual objects are picture elements in digital images. In particular, this problem is solved in terms of the application of rough sets in proximity spaces. The basic approach is to consider the nearness of the upper and lower approximation of a set introduced by Z. Pawlak during the early 1980s as a foundation for rough sets. Two forms of nearness relations are …considered, namely, a spatial EF- and a descriptive EF-relation. This leads to a study of the nearness of objects either spatially or descriptively in the approximation of a set. The nearness approximation space model developed in 2007 is refined and extended in this paper, leading to new forms of nearness approximation spaces. There is a natural transition from the two forms of nearness relations introduced in this article to the study of nearness granules. Show more

Keywords: Approximation space, EF-proximity space, nearness granule, nearness relation, rough sets, visual objects

DOI: 10.3233/FI-2013-939

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 159-176, 2013

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. The parser has many useful properties, and with the use of memoization, it works in a linear time. In its appearance, PEG is almost identical to a grammar in Extended Backus-Naur Form (EBNF), but usually defines a different language. However, in some cases only minor typographical changes are sufficient to convert an EBNF grammar into its PEG parser. As recently shown by Medeiros, this is, in particular, true for LL(1) grammars. But this is also true for many non-LL(1) grammars, which is interesting because the backtracking of PEG is …often a convenient way to circumvent just the LL(1) restriction. We formulate a number of conditions for EBNF grammar to become its own PEG parser, and arrive at a condition that we call LL(1p), meaning that a top-down parser can choose its next action by looking at the input within the reach of one parsing procedure (rather than by looking at the next letter). An extension to LL(kp) for k > 1 seems possible. Show more

DOI: 10.3233/FI-2013-940

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 177-191, 2013

Authors: Suraj, Zbigniew

Article Type: Research Article

Abstract: This paper presents a new class of Petri nets called generalised fuzzy Petri nets. The new class extends the existing fuzzy Petri nets by introducing three operators in the form of triangular norms, which are supposed to function as substitute for the min, max and * (algebraic product) operators. To demonstrate the power and the usefulness of this model, an application of the generalised fuzzy Petri nets in the domain of train traffic control is provided. The new model is more flexible than the classical one as in the former class the user has the chance to define the input/output …operators. The proposed approach can be used for knowledge representation and reasoning in decision support systems. Show more

Keywords: fuzzy Petri nets, knowledge representation, approximate reasoning, decision support Systems

DOI: 10.3233/FI-2013-941

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 193-207, 2013

Authors: Wagler, Annegret K. | Wegener, Jan-Thierry

Article Type: Research Article

Abstract: The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives fitting the given data. To keep the solution set small while guaranteeing its completeness, the idea is to generate only Petri nets being “minimal” in the sense that all other networks fitting the data contain the reconstructed ones. In this paper, we consider Petri nets with extensions in two directions: priority relations among the transitions of a network in order to allow modeling deterministic systems, and control-arcs in order to represent catalytic or inhibitory …dependencies. We define a containment relation for Petri nets taking both concepts, priority relations and control-arcs, into account. We discuss the consequences for this kind of Petri nets differing in their sets of control-arcs and priority relations, and the impact of our results towards the reconstruction of such Petri nets. Show more

DOI: 10.3233/FI-2013-942

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 209-222, 2013

Authors: Wolski, Marcin | Gomolińska, Anna

Article Type: Research Article

Abstract: Representation theory is a branch of mathematics whose original purpose was to represent information about abstract algebraic structures by means of methods of linear algebra (usually, by linear transformations and matrices). G.-C. Rota in his famous Foundations defined a representation of a locally finite partially ordered set (locally finite poset) P in terms of a module over a ring $\mathbb{A}$ , which can further be extended by the addition of a convolution operation to an associative $\mathbb{A}$ -algebra called an incidence algebra of P. He applied this construction to solve a number of important problems in combinatorics. Our …goal in this paper is to discuss the concept of an incidence algebra as a representation of a Pawlak information system. We shall analyse both incidence algebras and information systems in the context of granular computing, a paradigm which has recently received a lot of attention in computer science. We discuss therefore the concept of an incidence algebra on two levels: the level of objects which form a preordered set and the level of information granules which form a poset. Since incidence algebras induced on these two levels are Morita equivalent, we may focus our attention on the incidence algebra of information granules. We take the lattice of closed ideals of this algebra, where the maximal elements serve as a representation of information granules. The poset of maximal closed ideals obtained in this way is isomorphic to the set of information granules of the Pawlak information system equipped with a natural information order. Show more

Keywords: Pawlak information system, granular computing, representation theory, incidence algebra

DOI: 10.3233/FI-2013-943

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 223-238, 2013

Authors: Yaskorska, Olena | Budzynska, Katarzyna | Kacprzak, Magdalena

Article Type: Research Article

Abstract: The paper proposes a dialogue system LND which brings together and unifies two traditions in studying dialogue as a game: the dialogical logic introduced by Lorenzen; and persuasion dialogue games as specified by Prakken. The first approach allows the representation of formal dialogues in which the validity of argument is the topic discussed. The second tradition has focused on natural dialogues examining, e.g., informal fallacies typical in real-life communication. Our goal is to unite these two approaches in order to allow communicating agents to benefit from the advantages of both, i.e., to equip them with the ability not only to …persuade each other about facts, but also to prove that a formula used in an argument is a classical propositional tautology. To this end, we propose a new description of the dialogical logic which meets the requirements of Prakken's generic specification for natural dialogues, and we introduce rules allowing to embed a formal dialogue in a natural one. We also show the correspondence result between the original and the new version of the dialogical logic, i.e., we show that a winning strategy for a proponent in the original version of the dialogical logic means a winning strategy for a proponent in the new version, and conversely. Show more

DOI: 10.3233/FI-2013-944

Citation: Fundamenta Informaticae, vol. 128, no. 1-2, pp. 239-253, 2013