Fundamenta Informaticae - Volume 156, issue 1

Authors: Bilotta, Stefano | Grazzini, Elisabetta | Pergola, Elisa

Article Type: Research Article

Abstract: In this paper we give a combinatorial interpretation of linear recurrences having constant coefficients. In particular, we describe a recursive construction for a language ℒ such that the words in ℒ having length n satisfy the given recurrence and avoid a cross-bifix-free set of patterns.

Keywords: Linear recurrence relations, Succession rules, Cross-bifix-free sets, Pattern avoidance

DOI: 10.3233/FI-2017-1595

Citation: Fundamenta Informaticae, vol. 156, no. 1, pp. 1-19, 2017

Authors: Ban, Ha Bang | Nguyen, Duc Nghia

Article Type: Research Article

Abstract: Minimum Latency Problem (MLP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, we investigate the global structure of the MLP solution space to propose a suitable meta-heuristic algorithm for the problem, which combines Tabu search (TS) and Variable Neighborhood Search (VNS). In the proposed algorithm, TS is used to prevent the search from getting trapped into cycles, and guide VNS to escape local optima. In a cooperative way, VNS is employed to generate diverse neighborhoods for TS. We also introduce a novel neighborhoods’ structure for VNS and present a constant time operation …for calculating the latency cost of each neighboring solution. Extensive numerical experiments and comparisons with the state of the art meta-heuristic algorithms in the literature show that the proposed algorithm is highly competitive, providing the new best solutions for several instances. Show more

Keywords: The minimum latency problem, Tabu search, Variable Neighborhood search

DOI: 10.3233/FI-2017-1596

Citation: Fundamenta Informaticae, vol. 156, no. 1, pp. 21-41, 2017

Authors: Kłopotek, Mieczysław

Article Type: Research Article

Abstract: This paper investigates the application of consensus clustering and meta-clustering to the set of all possible partitions of a data set. We show that when using a “complement” of Rand Index as a measure of cluster similarity, the total-separation partition, putting each element in a separate set, is chosen.

Keywords: cluster analysis, partitioning, clustering, consensus functions, ensemble, knowledge reuse, unsupervised learning, meta-clustering

DOI: 10.3233/FI-2017-1597

Citation: Fundamenta Informaticae, vol. 156, no. 1, pp. 43-68, 2017

Authors: Mignot, Ludovic | Sebti, Nadia Ouali | Ziadi, Djelloul

Article Type: Research Article

Abstract: There exist several methods of computing an automaton recognizing the language denoted by a given regular expression: In the case of words, the position automaton 𝒫 due to Glushkov, the c-continuation automaton 𝒞 due to Champarnaud and Ziadi, the follow automaton ℱ due to Ilie and Yu and the equation automaton ɛ due to Antimirov. It has been shown that 𝒫 and 𝒞 are isomorphic and that ɛ (resp. ℱ ) is a quotient of 𝒞 (resp. of 𝒫 ). In this paper, we define from a given regular tree expression …the position tree automaton 𝒫 and the follow tree automaton ℱ . Using the definition of the equation tree automaton ɛ of Kuske and Meinecke and our previously defined c-continuation tree automaton 𝒞 , we show that the previous morphic relations are still valid on tree expressions. Show more

Keywords: tree automata constructions, regular tree expression, derivatives, partial derivatives, automata theory, c-continuations

DOI: 10.3233/FI-2017-1598

Citation: Fundamenta Informaticae, vol. 156, no. 1, pp. 69-94, 2017

Authors: Sroka, Jacek | Hidders, Jan

Article Type: Research Article

Abstract: This paper presents a notion of reduction where a WF net is transformed into a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more of such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantic properties such as soundness, can help with analysing and understanding why a WF net is sound or not. The reduction can also be used to verify if a WF net is an AND-OR net. This class of WF nets was introduced in earlier work, and arguably describes nets that …follow good hierarchical design principles. It is shown that the reduction is confluent up to isomorphism, which means that despite the inherent non-determinism that comes from the choice of subnets that are contracted, the final result of the reduction is always the same up to the choice of the identity of the nodes. Based on this result, a polynomial-time algorithm is presented that computes this unique result of the reduction. Finally, it is shown how this algorithm can be used to verify if a WF net is an AND-OR net. Show more

DOI: 10.3233/FI-2017-1599

Citation: Fundamenta Informaticae, vol. 156, no. 1, pp. 95-123, 2017