A one-sided Zimin construction.
A partially persistent data structure for the set-union problem
A periodicity property of iterated morphisms
Suppose ƒ : X* → X* is a morphism and u,v ∈ X*. For every nonnegative integer n, let zn be the longest common prefix of ƒn(u) and ƒn(v), and let un,vn ∈ X* be words such that ƒn(u) = znun and ƒn(v) = znvn. We prove that there is a positive integer q such that for any positive integer p, the prefixes of un (resp. vn) of length p form an ultimately periodic sequence having period q. Further, there is a value of q which works for all words u,v ∈ X*.
A Recursive Algorithm for the Maximum Cardinality Independent set
A reformulation of matrix graph grammars with Boolean complexes.
A remark on morphic sturmian words
A scaling result for explosive processes.
A simple algorithm for constructing Szemerédi's regularity partition.
A simple algorithm for the calculation of the characteristic polynomial and the eigenvalues of a hexagonal tape. (Ein einfacher Algorithmus zur Berechnung des charakteristischen Polynoms und der Eigenvectoren eines hexagonalen Bandes.)
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown....
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is...
A split&push approach to orthogonal drawing.
A survey of the algorithmic properties of simplicial, upper bound and middle graphs.
A syntactic characterization of bounded-rank decision trees in terms of decision lists
A test-set for -power-free binary morphisms
A morphism is -power-free if and only if is -power-free whenever is a -power-free word. A morphism is -power-free up to if and only if is -power-free whenever is a -power-free word of length at most . Given an integer , we prove that a binary morphism is -power-free if and only if it is -power-free up to . This bound becomes linear for primitive morphisms: a binary primitive morphism is -power-free if and only if it is -power-free up to
A test-set for k-power-free binary morphisms
A morphism f is k-power-free if and only if f(w) is k-power-free whenever w is a k-power-free word. A morphism f is k-power-free up to m if and only if f(w) is k-power-free whenever w is a k-power-free word of length at most m. Given an integer k ≥ 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k2. This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1
A theorem of Cobham for non-primitive substitutions
A Unified Approach to Visibility Representations of Planar Graphs.
A user study in similarity measures for graph drawing.
A van der Waerden variant.