Search

This paper presents a practical decision procedure for Propositional Projection Temporal Logic with infinite models. First, a set Prop l of labels l i , 0 ⩽ i ⩽ n ∈ N 0 , is used to mark nodes of an LNFG of a formula, and a node with l i is treated as an accepting state as in an automaton. Further, the generalized Büchi accepting condition for automata is employed to identify a path (resulting a word) in an LNFG as a model of the formula. In addition, the implementation details of the decision procedure and relevant algorithms including pre-processing, LNFG, circle finding algorithms are presented; as a matter of fact, all algorithms are implemented by C++ programs. [ABSTRACT FROM AUTHOR]

Abstract: Given a universe containing elements and a collection of multisets or sets over , the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in time and polynomial space, where is the maximum coverage requirement and denotes the total number of given multisets over . (The notation suppresses a factor polynomial in .) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusion–exclusion principle, we can exactly solve the SMC without multiplicity constraints problem in time. Compared with two recent results, in [Q.-S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multi-covering via inclusion–exclusion, Theoretical Computer Science, 410 (38–40) (2009) 3882–3892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in time and space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

Abstract: The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in time, where is the total number of ordered pairs of positions at which the two strings match and is the fixed gap constraint. We then improve the running time to using some novel techniques. Furthermore, we present an algorithm that is independent of and runs in time. Using these techniques, we also present a new algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to . Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. . But our results can be easily extended to handle two strings of different length. [Copyright &y& Elsevier]