Fundamenta Informaticae - Volume 141, issue 4

Authors: Basu, Tanmay | Murthy, C. A.

Article Type: Research Article

Abstract: The similarity based decision rule computes the similarity between a new test document and the existing documents of the training set that belong to various categories. The new document is grouped to a particular category in which it has maximum number of similar documents. A document similarity based supervised decision rule for text categorization is proposed in this article. The similarity measure determine the similarity between two documents by finding their distances with all the documents of training set and it can explicitly identify two dissimilar documents. The decision rule assigns a test document to the best one among the …competing categories, if the best category beats the next competing category by a previously fixed margin. Thus the proposed rule enhances the certainty of the decision. The salient feature of the decision rule is that, it never assigns a document arbitrarily to a category when the decision is not so certain. The performance of the proposed decision rule for text categorization is compared with some well known classification techniques e.g., k-nearest neighbor decision rule, support vector machine, naive bayes etc. using various TREC and Reuter corpora. The empirical results have shown that the proposed method performs significantly better than the other classifiers for text categorization. Show more

Keywords: Document Similarity, Text Categorization, Decision Rule, Text Mining

DOI: 10.3233/FI-2015-1276

Citation: Fundamenta Informaticae, vol. 141, no. 4, pp. 275-295, 2015

Authors: Bortolussi, Luca | Dinu, Liviu P. | Franzoi, Laura | Sgarro, Andrea

Article Type: Research Article

Abstract: We put forward an ample framework for coding based on upper probabilities, or more generally on normalized monotone set-measures, and model accordingly noisy transmission channels and decoding errors. Two inverse problems are considered. In the first case, a decoder is given and one looks for channels of a specified family over which that decoder would work properly. In the second and more ambitious case, it is codes which are given, and one looks for channels over which those codes would ensure the required error correction capabilities. Upper probabilities allow for a solution of the two inverse problems in the case …of usual codes based on checking Hamming distances between codewords: one can equivalently check suitable upper probabilities of the decoding errors. This soon extends to “odd” codeword distances for DNA strings as used in DNA word design, where instead, as we prove, not even the first unassuming inverse problem admits of a solution if one insists on channel models based on “usual” probabilities. Show more

Keywords: Shannon theory, coding theory, decoding errors, upper probabilities

DOI: 10.3233/FI-2015-1277

Citation: Fundamenta Informaticae, vol. 141, no. 4, pp. 297-310, 2015

Authors: Dicky, Anne | Janin, David

Article Type: Research Article

Abstract: We consider classes of languages of overlapping tiles, i.e., subsets of the McAlister monoid: the class REG of languages definable by Kleene’s regular expressions, the class MSO of languages definable by formulas of monadic second-order logic, and the class REC of languages definable by morphisms into finite monoids. By extending the semantics of finite-state two-way automata (possibly with pebbles) from languages of words to languages of tiles, we obtain a complete characterization of the classes REG and MSO . In particular, we show that adding pebbles strictly increases the expressive power of two-way automata recognizing languages …of tiles, but the hierarchy induced by the number of allowed pebbles collapses to level one. Show more

Keywords: two-way automata, word languages, overlapping tile languages, regular languages, McAlister inverse monoid

DOI: 10.3233/FI-2015-1278

Citation: Fundamenta Informaticae, vol. 141, no. 4, pp. 311-343, 2015

Authors: Durnoga, Konrad | Źrałek, Bartosz

Article Type: Research Article

Abstract: We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor – a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they …rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giant-step method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine. Show more

DOI: 10.3233/FI-2015-1279

Citation: Fundamenta Informaticae, vol. 141, no. 4, pp. 345-366, 2015

Authors: Sroka, Jacek | Chrząstowski-Wachtel, Piotr | Hidders, Jan

Article Type: Research Article

Abstract: For designing and analyzing complex workflow nets the notion of hierarchical decomposition can be essential for keeping the structure of the workflow comprehensible. In this paper we study two classes of nets: hierarchical nets and extended hierarchical nets. The first have a simple hierarchical structure and can be defined in terms of five simple refinement rules. We show that for arbitrary nets it can be easily verified if they can be constructed this way, thus confirming their good design and the properties following from it. As we prove, this can be done by performing the refinements in reverse, i.e., by …contracting subnets into single nodes. It is shown that the choice of the contracted subnet does not change the final result of the process, and therefore this procedure for checking the hierarchical structure requires no back-tracking. The second class, extended hierarchical nets, is an extension of the first class where two types of extra refinements are introduced that allow to indicate (1) the synchronization between two parallel running subworkflows or (2) the transfer of a thread from one subworkflow to another one. These refinements come with natural and necessary preconditions that ensure that result is still a sound workflow net. In case (1) where we want to synchronize two actions in two subworkflows, we should convince ourselves that the subworkflows represent parallel threads which always execute together, otherwise a deadlock could easily arise. Dually, in case (2), if after the moment that a choice was made between two subworkflows we at a later point in the workflow want to allow a transfer between them, this can be done safely provided that we did not enter any thread fork in the meantime. We show that the class of extended hierarchical nets, which is defined by adding these two additional types of refinement, is a proper superset of the hierarchical nets, but still all such nets exhibit the correctness property of *-soundness. We do this by showing that the class is a proper subset of the AND-OR nets which were in earlier work shown to have this property. Show more

Keywords: workflow net, Petri net, soundness, *-soundness, hierarchical nets, extended hierarchical nets

DOI: 10.3233/FI-2015-1280

Citation: Fundamenta Informaticae, vol. 141, no. 4, pp. 367-398, 2015

Article Type: Other

Citation: Fundamenta Informaticae, vol. 141, no. 4, pp. 399-400, 2015