Fundamenta Informaticae - Volume 111, issue 4

Authors: Champarnaud, Jean-Marc | Farré, Jacques | Guingne, Franck

Article Type: Research Article

Abstract: Finite languages and finite subsequential functions can be represented by possibly cyclic finite machines, respectively called cover automata and cover transducers. Reduced cover machines can have fewer states than the corresponding minimal machines, yielding a compact representation for lexicons or dictionaries. We present here a new algorithm for reducing the number of states of an acyclic transducer.

Keywords: Finite subsequential function, Acyclic transducer, Cover transducer

DOI: 10.3233/FI-2011-567

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 357-371, 2011

Authors: Deng, Zhi-Hong | Gao, Ning | Xu, Xiao-Ran

Article Type: Research Article

Abstract: Mining frequent patterns in database has emerged as an important task in knowledge discovery and data mining. In this paper, we present an efficient algorithm called Mop for fast frequent pattern discovery. Mop utilizes a new kind of data structure called OP_tree (ordered pattern tree) and some particular properties of frequent patterns to facilitate the process of mining frequent patterns. An OP_tree is a special frequent pattern tree, where the children of any node are sorted according to the supports of corresponding items. Efficiency of Mop is achieved with three techniques: (1) it adopts OP_tree to store a large database …to avoid repetitive database scans, (2) it finds all frequent 2-patterns in the construction of OP_tree to avoid the costly generation of a large number of candidate 2-patterns, (3) the supports of candidate k-patterns (k>2) can be obtained by traversing a few of specific subtrees of the OP_tree, which greatly reduces the search space and avoid multi-scans of a database. We experimentally compare our algorithm with the Apriori algorithm and the FP-growth algorithm on one real database and one synthetical database. The experimental results show that Mop is about an order of magnitude faster than the Apriori algorithm. Mop also outperforms the FP-growth algorithm, especially when support threshold is very low and databases are quite large. Show more

Keywords: Data Mining, Frequent Patterns, Ordered Pattern Trees

DOI: 10.3233/FI-2011-568

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 373-390, 2011

Authors: Gandhi, Aniruddh | Khoussainov, Bakhadyr | Liu, Jiamou

Article Type: Research Article

Abstract: This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Büchi games played on trees with back-edges in time O(min{r·m, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees …with back-edges can be solved in time O(l + m). Show more

Keywords: Büchi games, trees with back-edges, snares, parity games, experiment

DOI: 10.3233/FI-2011-569

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 391-412, 2011

Authors: Garg, Manish | Gangopadhyay, Sugata

Article Type: Research Article

Abstract: In this paper we find a lower bound of the second-order nonlinearities of Boolean bent functions of the form ${\rm f}({\rm x}) = {\rm Tr}_{1}^{{\rm n}}(\rmalpha_{1}{\rm x}^{{\rm d}_{1}} + \rmalpha_{2}{\rm x}^{{\rm d}_{2}})$, where d1 and d2 are Niho exponents. A lower bound of the second-order nonlinearities of these Boolean functions can also be obtained by using a recent result of Li, Hu and Gao (eprint.iacr.org/2010 /009.pdf). It is shown in Section 3, by a direct computation, that for large values of n, the lower bound obtained in this paper are better than the lower bound obtained by Li, …Hu and Gao. Show more

Keywords: Boolean function, Derivative, Niho power function, Second-order nonlinearity, Walsh-spectrum

DOI: 10.3233/FI-2011-570

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 413-422, 2011

Authors: Ionescu, Mihai | Păun, Gheorghe | Pérez-Jiménez, Mario J. | Yokomori, Takashi

Article Type: Research Article

Abstract: We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they …can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open. Show more

DOI: 10.3233/FI-2011-571

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 423-436, 2011

Authors: Kisielewicz, Andrzej | Szykuła, Marek

Article Type: Research Article

Abstract: Given a graph H we define ρ(H) to be the minimum order of a graph G such that every proper vertex coloring of G contains a rainbow induced subgraph isomorphic to H. We give upper and lower bounds for ρ(H), compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of ρ(H) for paths. A part of this research has been guided by a computer search and, accordingly, some computational results are presented. A special motivation comes from research in on-line coloring.

Keywords: rainbow, induced subgraph, vertex coloring, replication graph, C++

DOI: 10.3233/FI-2011-572

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 437-451, 2011

Authors: Nishida, Taishin Yasunobu

Article Type: Research Article

Abstract: In this paper we show that for every k-block morphism (k ≥ 2) there is a spiking neural P system which computes the morphism. This result generalises the result explored by G. Păun, M. Pérez-Jiménez, and G. Rozenberg. We give an algorithm which constructs the spiking neural P system, that is, if a k-block morphism is given as an input, the algorithm makes rules of the spiking neural P system which computes the morphism.

Keywords: spiking neural P system, k-block morphism

DOI: 10.3233/FI-2011-573

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 453-464, 2011

Article Type: Other

Citation: Fundamenta Informaticae, vol. 111, no. 4, pp. 465-466, 2011