Add to ORKGAbstract. Directed Acyclic Subsequence Graph is an automaton, which ac-cepts all subsequences of the given string. We introduce a left-to-right algorithm for incremental construction of DASG. The algorithm requires O(z) extra space and O(nz log z) time for arbitrary alphabet (O(nz) for xed alphabet), where z = min(jj; n). The number of transitions can be reduced by encoding input symbols using k digits, where k < min(jj; n). We introduce a left-to-right algorithm for incremental construction of DASG for k = 2. We show the ex-tension of the algorithm for the set of strings and its application for the longest common subsequence problem
AbstractIn this paper, we present linear-time algorithms for the construction two novel types of fin...
In this paper we look at the problem of generating code with instruction chaining from directed acyc...
AbstractShortest path problems can be solved very efficiently when a directed graph is nearly acycli...
AbstractThe subsequence matching problem is to decide, for given strings S and T, whether S is a sub...
AbstractWe define the directed acyclic subsequence graph of a text as the smallest deterministic par...
This paper shows that a simple algorithm produces the all-prefixes-LCSs-graph in O(mn) time for two ...
A new algorithm that creates a common subsequence automaton for a set of strings is presented. Moreo...
Abstract. A non-linear text is a directed graph where each vertex is labeled with a string. In this ...
Given a set of strings, the Common Subsequence Automaton accepts all common subsequences of these st...
A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a ...
AbstractLet G be a directed acyclic graph, each vertex of which is labeled with a symbol, and having...
Given two strings X and Y of lengths m and n, re-spectively, the all-substrings longest common subse...
summary:An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DA...
We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the ...
This paper presents new algorithms for computing shortest paths in a nearly acyclic directed graph G...
AbstractIn this paper, we present linear-time algorithms for the construction two novel types of fin...
In this paper we look at the problem of generating code with instruction chaining from directed acyc...
AbstractShortest path problems can be solved very efficiently when a directed graph is nearly acycli...
AbstractThe subsequence matching problem is to decide, for given strings S and T, whether S is a sub...
AbstractWe define the directed acyclic subsequence graph of a text as the smallest deterministic par...
This paper shows that a simple algorithm produces the all-prefixes-LCSs-graph in O(mn) time for two ...
A new algorithm that creates a common subsequence automaton for a set of strings is presented. Moreo...
Abstract. A non-linear text is a directed graph where each vertex is labeled with a string. In this ...
Given a set of strings, the Common Subsequence Automaton accepts all common subsequences of these st...
A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a ...
AbstractLet G be a directed acyclic graph, each vertex of which is labeled with a symbol, and having...
Given two strings X and Y of lengths m and n, re-spectively, the all-substrings longest common subse...
summary:An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DA...
We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the ...
This paper presents new algorithms for computing shortest paths in a nearly acyclic directed graph G...
AbstractIn this paper, we present linear-time algorithms for the construction two novel types of fin...
In this paper we look at the problem of generating code with instruction chaining from directed acyc...
AbstractShortest path problems can be solved very efficiently when a directed graph is nearly acycli...