Finite-state computability of annotations of strings and trees (extended abstract): Combinatorial Pattern Matching

Hans Bodlaender, Michael R. Fellows, Patricia A. Evans

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review


An annotation of a string X over an alphabet Σ is a string Y having the same length as X, over an alphabet Γ. The pair (X, Y) can be viewed as a string over the alphabet Σ×Γ. The search problem for a language L ⊑ (Σ × Γ) * is the problem of computing, given a string X ∈ Σ*, a string Y ∈ Γ*, having the same length as X, such that (X, Y) ∈ L, or determining that no such Y exists. We define a notion of finitestate searchability and prove the following (main) theorem: If L is finitestate recognizable, then it is finitestate searchable. The notions of annotation and finite-state searchability can be generalized to trees of symbols. Annotation search problems have a variety of applications. For example, the tree or string of symbols may represent the structural parse of a graph of bounded treewidth or pathwidth, and the annotation may represent a “solution” to a search problem (e.g., finding a subgraph homeomorphic to a fixed graph H). Our main theorem allows us to treat in a general and natural way the search problems that correspond to the many important graph decision problems now known to be solvable in linear time for graphs of bounded treewidth and pathwidth. As a corollary, we show finite-state searchability for graph properties whose solutions can be expressed by leading existential quantification in monadic second-order logic. This can be viewed as a “search problem” form of Courcelle's Theorem on the decidability of monadic second-order graph properties. We describe several possible applications to computing annotations of biological sequences, and discuss how the resulting annotations may be useful in sequence comparison and alignment.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication7th Annual Symposium, CPM 96 Laguna Beach, California, June 10–12, 1996 Proceedings
EditorsDan Hirschberg, Gene Myers
Number of pages8
ISBN (Print)978-3-540-61258-2
Publication statusPublished - 1996

Publication series

NameLecture Notes in Computer Science


Dive into the research topics of 'Finite-state computability of annotations of strings and trees (extended abstract): Combinatorial Pattern Matching'. Together they form a unique fingerprint.

Cite this