Fundamenta Informaticae - Volume 159, issue 3

Authors: de Boer, Frank S. | Bravetti, Mario | Lee, Matias D. | Zavattaro, Gianluigi

Article Type: Research Article

Abstract: We give two different notions of deadlock for systems based on active objects and futures. One is based on blocked objects and conforms with the classical definition of deadlock by Coffman, Jr. et al. The other one is an extended notion of deadlock based on blocked processes which is more general than the classical one. We introduce a technique to prove deadlock freedom of systems of active objects. To check deadlock freedom an abstract version of the program is translated into Petri nets. Extended deadlocks, and then also classical deadlock, can be detected via checking reachability of a distinct marking. …Absence of deadlocks in the Petri net constitutes deadlock freedom of the concrete system. Show more

Keywords: Petri nets, active objects, deadlock analysis

DOI: 10.3233/FI-2018-1663

Citation: Fundamenta Informaticae, vol. 159, no. 3, pp. 197-256, 2018

Authors: Ikegami, Kenshin | Ohsawa, Yukio

Article Type: Research Article

Abstract: It is useful to extract review sentences based on an assigned viewpoint for purposes such as summarization tasks. Previous studies have considered review extraction using semi-supervised learning or association mining. However, we approach this task using a clustering method. In particular, we focus on a topic model as a clustering method. In the conventional topic model, after randomly initializing the word distribution and the topic distribution, these distributions are estimated in order to minimize the perplexity using Gibbs sampling or variational Bayes. We introduce a new method called the PageRank topic model (PRTM) for estimating multinomial distributions over topics and …words using network structure analysis methods. PRTM extracts topics by focusing on the co-occurrence relationships of words and it does not need randomly initialized values. Therefore, it can calculate unique word and topic distributions. In experiments using synthetic data, we showed that PRTM can infer an appropriate number of topics by clustering short sentences, and it was particularly effective when the sentences were covered by a small number of topics. Furthermore, in a real-world review data experiment, we showed that PRTM performed better with a shorter runtime compared with other models that infer the number of topics. Show more

Keywords: network analysis, review data, sentence clustering, topic model

DOI: 10.3233/FI-2018-1664

Citation: Fundamenta Informaticae, vol. 159, no. 3, pp. 257-277, 2018

Authors: Salehi, Saeed

Article Type: Research Article

Abstract: The multiplicative theory of a set of numbers (which could be natural, integer, rational, real or complex numbers) is the first-order theory of the structure of that set with (solely) the multiplication operation (that set is taken to be multiplicative, i.e., closed under multiplication). In this paper we study the multiplicative theories of the complex, real and (positive) rational numbers. These theories (and also the multiplicative theories of natural and integer numbers) are known to be decidable (i.e., there exists an algorithm that decides whether a given sentence is derivable form the theory); here we present explicit axiomatizations for them …and show that they are not finitely axiomatizable. For each of these sets (of complex, real and [positive] rational numbers) a language, including the multiplication operation, is introduced in a way that it allows quantifier elimination (for the theory of that set). Show more

Keywords: Decidability, Completeness, Multiplicative Theory, Quantifier Elimination

DOI: 10.3233/FI-2018-1665

Citation: Fundamenta Informaticae, vol. 159, no. 3, pp. 279-296, 2018

Authors: Sarkar, Apurba | Biswas, Arindam | Dutt, Mousumi | Mondal, Shouvick

Article Type: Research Article

Abstract: This article presents a combinatorial algorithm to find a shortest triangular path (STP) between two points inside a digital object imposed on triangular grid that runs in O ( n g log n g ) time, where n is the number of pixels on the contour of the object and g is the grid size. Initially, the inner triangular cover which maximally inscribes the object is constructed to ensure that the path lies within the object. An appropriate bounding parallelogram is considered with those two points in diagonally opposite corners …and then one of the semi-perimeters of the parallelogram is traversed. Certain combinatorial rules are formulated based on the properties of triangular grid and are applied during the traversal whenever required to shorten the triangular path. A shortest triangular path between any two points may not be unique. Another combinatorial algorithm is presented, which finds the family of shortest triangular path (FSTP) (i.e., the region containing all possible shortest triangular paths) between two given points inside a digital object and runs in O ( n g log n g ) time. Experimental results are presented to verify the correctness, robustness, and efficacy of the algorithms. STP and FSTP can be useful for shape analysis of digital objects and determining shape signatures.1 Show more

DOI: 10.3233/FI-2018-1666

Citation: Fundamenta Informaticae, vol. 159, no. 3, pp. 297-325, 2018