Fundamenta Informaticae - Volume 130, issue 2

Authors: Luong, Chi Mai | Piuri, Vincenzo | Nguyen, Hung Son

Article Type: Other

DOI: 10.3233/FI-2014-985

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. i-iii, 2014

Authors: Han, Nguyen Dinh | Vinh, Ho Ngoc | Thang, Dang Quyet | Huy, Phan Trung

Article Type: Research Article

Abstract: The Sardinas-Patterson's test for codes has contributed many effective testing algorithms to the development of theory of codes, formal languages, etc. However, we will show that a modification of this test proposed in this paper can deduce more effective testing algorithms for codes. As a consequence, we establish a quadratic algorithm that, given as input a regular language X defined by a tuple (�, M, B), where � : A* → M is a monoid morphism saturating X, M is a finite monoid, $B \subseteq M$, X = �−1 (B), decides in time complexity $\mathcal{O}(n^2)$ whether X is a code, …where n = Card(M). Specially, n can be chosen as the finite index of X. A quadratic algorithm for testing of ◊-codes is also established. Show more

Keywords: Sardinas-Patterson, quadratic algorithm, monoid, code, ◊-code

DOI: 10.3233/FI-2014-986

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. 163-177, 2014

Authors: Hoang, Cuong | Le, Anh-Cuong | Nguyen, Phuong-Thai | Pham, Son Bao | Ho, Tu Bao

Article Type: Research Article

Abstract: Automatically building a large bilingual corpus that contains millions of words is always a challenging task. In particular in case of low-resource languages, it is difficult to find an existing parallel corpus which is large enough for building a real statistical machine translation. However, comparable non-parallel corpora are richly available in the Internet environment, such as in Wikipedia, and from which we can extract valuable parallel texts. This work presents a framework for effectively extracting parallel sentences from that resource, which results in significantly improving the performance of statistical machine translation systems. Our framework is a bootstrapping-based method that is …strengthened by using a new measurement for estimating the similarity between two bilingual sentences. We conduct experiment for the language pair of English and Vietnamese and obtain promising results on both constructing parallel corpora and improving the accuracy of machine translation from English to Vietnamese. Show more

Keywords: Parallel sentence extraction, non-parallel comparable corpora, statistical machine translation

DOI: 10.3233/FI-2014-987

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. 179-199, 2014

Authors: Lai, Hien Phuong | Visani, Muriel | Boucher, Alain | Ogier, Jean-Marc

Article Type: Research Article

Abstract: The feature space structuring methods play a very important role in finding information in large image databases. They organize indexed images in order to facilitate, accelerate and improve the results of further retrieval. Clustering, one kind of feature space structuring, may organize the dataset into groups of similar objects without prior knowledge (unsupervised clustering) or with a limited amount of prior knowledge (semi-supervised clustering). In this paper, we present both formal and experimental comparisons of different unsupervised clustering methods for structuring large image databases. We use different image databases of increasing sizes (Wang, PascalVoc2006, Caltech101, Corel30k) to study the scalability …of the different approaches. Then, we present a new interactive semi-supervised clustering model, which allows users to provide feedback in order to improve the clustering results according to their wishes. Moreover,we also compare, experimentally, our proposed model with the semi-supervised HMRF-kmeans clustering method. Show more

Keywords: Unsupervised clustering, semi-supervised clustering, interactive learning

DOI: 10.3233/FI-2014-988

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. 201-218, 2014

Authors: Nguyen, Ngoc Trung | Duong, Anh-Duc

Article Type: Research Article

Abstract: We consider the following problem: Given n red points, m green points and p blue points on a plane, find a trio of red-green-blue points such that the distance between them is smallest. This problem could be solved by an exhaustive search algorithm: test all trios of 3 different colored points and find the closest trio. However, this algorithm has the complexity of O(N3 ), N = max(n, p, q). In our previous research, we already showed a heuristic algorithm with a good complexity to solve this problem based on 2D Voronoi diagram. In this paper, we introduce a better …heuristic algorithm for solving this problem. This new heuristic algorithm has the same complexity but it performs much better than the old one. Show more

Keywords: colored points, Voronoi diagram, min-max problem

DOI: 10.3233/FI-2014-989

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. 219-229, 2014

Authors: Pham, San | Gascon, Viviane | Dinh, Tien

Article Type: Research Article

Abstract: To maintain patients at home as most as possible, healthcare services are nowadays quite diversified. We present the case of a public medical clinic offering activities, mostly to the elderly, at a daycare center. Users are brought into the daycare center by bus or by taxi. The global problem consists in defining routes to pick up users while assigning them to time slots in the week. At first sight this problem could be viewed as an asymmetric multiple vehicle routing problem. However many additional constraints must be considered. In this paper, we propose a metaheuristic including two phases to solve …the problem. In the first phase, the initial solution is determined using one of two proposed constructed algorithms and is improved using tabu search in the second phase. These algorithms are tested on 10 problem instances. Experimental results are presented. Show more

Keywords: vehicle routing problem, sweep algorithm, saving heuristic, tabu search

DOI: 10.3233/FI-2014-990

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. 231-246, 2014

Authors: Thanh, Tran Thang | Chen, Fan | Kotani, Kazunori | Le, Bac

Article Type: Research Article

Abstract: Emergence of novel techniques devices e.g., MS Kinect, enables reliable extraction of human skeletons from action videos. Taking skeleton data as inputs, we propose an approach to extract the discriminative patterns for efficient human action recognition. Each action is considered to consist of a sequence of unit actions, each of which is represented by a pattern. Given a skeleton sequence, we first automatically extract the key-frames, and then categorize them into different patterns. We further use a statistical metric to evaluate the discriminative capability of patterns, and define them as local features for action recognition. Experimental results show that the …extracted local descriptors could provide very high accuracy in the action recognition, which demonstrate the efficiency of our method in extracting discriminative unit actions. Show more

Keywords: Discriminative Patterns, 3D Skeletons, Local Descriptor, Improved TF-IDF, Action Recognition

DOI: 10.3233/FI-2014-991

Citation: Fundamenta Informaticae, vol. 130, no. 2, pp. 247-261, 2014