Warshall's algorithm -- survey and applications
---
paper_title: Versatile string kernels

paper_content:

This paper proposes a class of string kernels that can handle a variety of subsequence-based features. Slight adaptations of the basic algorithm allow for weighing subsequence lengths, restricting or soft-penalizing gap-size, character-weighing and soft-matching of characters. An easy extension of the kernels allows for comparing run-length encoded strings with a time-complexity that is independent of the length of the original strings. Such kernels have applications in image processing, computational biology, in demography and in comparing partial rankings.
---

Title: Warshall's Algorithm -- Survey and Applications

Section 1: Introduction
Description 1: Provide an overview and basic explanation of Warshall's algorithm and its purpose in computing the transitive closure of a binary relation.

Section 2: Generalization of Warshall's Algorithm
Description 2: Explore the generalized version of Warshall's algorithm using operations from a semiring, and discuss applications including the Floyd-Warshall algorithm.

Section 3: Number of Paths in Acyclic Digraphs
Description 3: Describe the algorithm for counting the number of paths between vertices in an acyclic digraph.

Section 4: All Paths in Digraphs
Description 4: Explain how the Warshall algorithm combined with the Latin square method can be used to find all paths in a digraph, including initializing the matrix and defining operations.

Section 5: Scattered Complexity for Rainbow Words
Description 5: Discuss the application of Warshall's algorithm to compute the scattered subword complexity of rainbow words using graph theoretical results.

Section 6: Special Paths in Finite Automata
Description 6: Investigate the use of Warshall's algorithm to find transitions between states in finite automata, including an example of the algorithm in use.