Fundamenta Informaticae - Volume 119, issue 3-4

Authors: Czaja, Ludwik

Article Type: Other

DOI: 10.3233/FI-2012-734

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. i-ii, 2012

Authors: Amin, Talha | Chikalov, Igor | Moshkov, Mikhail | Zielosko, Beata

Article Type: Research Article

Abstract: This paper is devoted to the study of an extension of dynamic programming approach which allows optimization of partial decision rules relative to the length or coverage. We introduce an uncertainty measure J(T) which is the difference between number of rows in a decision table T and number of rows with the most common decision for T. For a nonnegative real number γ, we consider γ-decision rules (partial decision rules) that localize rows in subtables of T with uncertainty at most γ. Presented algorithm constructs a directed acyclic graph Δγ (T) which nodes are subtables of the decision table T …given by systems of equations of the kind “attribute = value”. This algorithm finishes the partitioning of a subtable when its uncertainty is at most γ. The graph Δγ (T) allows us to describe the whole set of so-called irredundant γ-decision rules. We can optimize such set of rules according to length or coverage. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository. Show more

Keywords: Partial decision rules, length, coverage, dynamic programming

DOI: 10.3233/FI-2012-735

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 233-248, 2012

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: FGCJ is a minimal core calculus that extends Featherweight Generic Java, FGJ, with lambda expressions for Java Simple Closures. It has been introduced to study, in a reduction semantics framework, properties of Java Simple Closures, including type safety and abstraction property. ℱ is a source-to-source, translation rule system from Java 1.5 extended with lambda expressions, back to ordinary Java 1.5. It has been introduced to study, in a translation semantics framework, the design and the implementation features of lambda expressions, including simple closures, this transparency, not local variables and relations with anonymous class objects. In this paper we prove that …the reduction semantics and the translation semantics commute in FGACJ. Where FGACJ is a minimal core calculus that extends FGCJ, by adding Java interfaces and anonymous class objects and that allows a restricted definition of translation semantics ℱ. Show more

DOI: 10.3233/FI-2012-736

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 249-264, 2012

Authors: Czaja, Ludwik

Article Type: Research Article

Abstract: A protocol of mutual exclusion with FIFO discipline is devised for distributed systems with Distributed Shared Memory (DSM) and without any central server. To this end, replication of data - a principal feature of DSM is exploited. Some data consistency is discussed.

DOI: 10.3233/FI-2012-737

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 265-280, 2012

Authors: Fioravanti, Fabio | Pettorossi, Alberto | Proietti, Maurizio | Senni, Valerio

Article Type: Research Article

Abstract: We consider infinite state reactive systems specified by using linear constraints over the integers, and we address the problem of verifying safety properties of these systems by applying reachability analysis techniques. We propose a method based on program specialization, which improves the effectiveness of the backward and forward reachability analyses. For backward reachability our method consists in: (i) specializing the reactive system with respect to the initial states, and then (ii) applying to the specialized system the reachability analysis that works backwards from the unsafe states. For reasons of efficiency, during specialization we make use of a relaxation from integers …to reals. In particular, we test the satisfiability or entailment of constraints over the real numbers, while preserving the reachability properties of the reactive systems when constraints are interpreted over the integers. For forward reachability our method works as for backward reachability, except that the role of the initial states and the unsafe states are interchanged. We have implemented our method using the MAP transformation system and the ALV verification system. Through various experiments performed on several infinite state systems, we have shown that our specialization-based verification technique considerably increases the number of successful verifications without a significant degradation of the time performance. Show more

Keywords: Reachability analysis, automatic verification, program transformation, constraint logic programming

DOI: 10.3233/FI-2012-738

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 281-300, 2012

Authors: Gomolińska, Anna | Wolski, Marcin

Article Type: Research Article

Abstract: In this article we present three inclusion functions which characterise the nearness relation between finite sets of objects defined in line with J. F. Peters, A. Skowron, and J. Stepaniuk [26]. By means of these functions we extend the notion of nearness to the graded case where one can measure the degree to which one set is near to another one.

Keywords: nearness of sets, topological point-to-set nearness, inclusion function, rough approximation, granular computing

DOI: 10.3233/FI-2012-739

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 301-317, 2012

Authors: Janusz, Andrzej | Ślęzak, Dominik | Nguyen, Hung Son

Article Type: Research Article

Abstract: This paper presents a research on the construction of a new unsupervised model for learning a semantic similarity measure from text corpora. Two main components of the model are a semantic interpreter of texts and a similarity function whose properties are derived from data. The first one associates particular documents with concepts defined in a knowledge base corresponding to the topics covered by the corpus. It shifts the representation of a meaning of the texts from words that can be ambiguous to concepts with predefined semantics. With this new representation, the similarity function is derived from data using a modification …of the dynamic rule-based similarity model, which is adjusted to the unsupervised case. The adjustment is based on a novel notion of an information bireduct having its origin in the theory of rough sets. This extension of classical information reducts is used in order to find diverse sets of reference documents described by diverse sets of reference concepts that determine different aspects of the similarity. The paper explains a general idea of the approach and also gives some implementation guidelines. Additionally, results of some preliminary experiments are presented in order to demonstrate usefulness of the proposed model. Show more

Keywords: Similarity learning, semantic similarity, text mining, feature extraction, bireducts

DOI: 10.3233/FI-2012-740

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 319-336, 2012

Authors: Leszczyński, Paweł | Stencel, Krzysztof

Article Type: Research Article

Abstract: In recent years, the scalability of web applications has become critical. Web sites get more dynamic and customized. This increases servers' workload. Furthermore, the future increase of load is difficult to predict. Thus, the industry seeks for solutions that scale well. With current technology, almost all items of system architectures can be multiplied when necessary. There are, however, problems with databases in this respect. The traditional approach with a single relational database has become insufficient. In order to achieve scalability, architects add a number of different kinds of storage facilities. This could be error prone because of inconsistencies in stored …data. In this paper we present a novel method to assemble systems with multiple storages. We propose an algorithm for update propagation among different storages like multi-column, key-value, and relational databases. Show more

Keywords: multi storage, scalability, key-value storage, column family storage, data consistency, web applications

DOI: 10.3233/FI-2012-741

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 337-355, 2012

Authors: Oshevskaya, Elena | Virbitskaite, Irina | Best, Eike

Article Type: Research Article

Abstract: The intention of the paper is to show how several categorical (open morphisms, path morphisms and coalgebraic morphisms based) approaches to an abstract characterization of bisimulation relate to each other and to behavioral bisimulations, in the setting of higher dimensional automata. Such a relating makes it possible to develop a metatheory designed for unified definition and study of equivalences in true concurrency semantics.

DOI: 10.3233/FI-2012-742

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 357-372, 2012

Authors: Penczek, Wojciech | Woźna-Szcześniak, Bożena | Zbrzezny, Andrzej

Article Type: Research Article

Abstract: This paper makes two contributions to the verification of multi-agent systems modelled by interleaved interpreted systems. Firstly, the paper presents theoretical underpinnings of the SAT-based bounded model checking (BMC) approach for LTL extended with the epistemic component (LTLK) over interleaved interpreted systems. Secondly, the BMC method has been implemented and tested on several benchmarks for MAS. The preliminary experimental results reveal advantages and disadvantages of our SAT-based BMC for LTLK and show that the method has a significant potential.

DOI: 10.3233/FI-2012-743

Citation: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 373-392, 2012