Window-accumulated subsequence matching problem is linear

DOI10.1016/S0168-0072(01)00051-3MaRDI QIDQ5957906zbMATH OpenFDO

Authors Luc Boasson, Patrick Cégielski, Irène Guessarian, Yu. Matiyasevich

Publication date 27 November 2002

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(01)00051-3

zbMATH Keywords

subsequence matching

Mathematics Subject Classification ID

Searching and sorting (68P10) Database theory (68P15)

Recommendations

• Multiple serial episodes matching
• Window Subsequence Problems for Compressed Texts
• Compact recognizers of episode sequences
• Worst case efficient single and multiple string matching in the RAM model
• Publication:3468609

Cites work

• An algorithm for string matching with a sequence of don't cares
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 4078846 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3594652 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 3403734 (Why is no real title available?)
• Matching a set of strings with variable length don't cares
• Multiplication, division, and shift instructions in parallel random access machines
• On the power of the shift instruction
• On-line construction of suffix trees
• Real-time recognition of the inclusion relation
• String Matching in Real Time

Cited in

(13)

• An efficient algorithm for attribute-based subsequence matching
• On trace inclusion optimization problems
• Inclusion problems in trace monoids
• Window Subsequence Problems for Compressed Texts
• Significant Subpatterns Matching
• Tree inclusion problems
• Near-optimal algorithm to count occurrences of subsequences of a given length
• Fundamentals of Computation Theory
• AWLCO: All-Window Length Co-Occurrence
• Combinatorial algorithms for subsequence matching: a survey
• Longest common substring with gaps and related problems
• Tree inclusions in windows and slices
• Multiple serial episodes matching

This page was built for publication: Window-accumulated subsequence matching problem is linear

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957906)