Disjoint pattern matching and implication in strings

DOI10.1016/J.IPL.2009.11.009zbMATH Open1209.68175OpenAlexW2006299584MaRDI QIDQ990133FDOQ990133

Cristina Sirangelo, Leonid Libkin

Publication date: 2 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.1811

Recommendations

• Implication of regular expressions
• Pattern matching with variables: fast algorithms and new hardness results
• Separating sets of strings by finding matching patterns is almost always hard
• scientific article; zbMATH DE number 7278096
• Pattern matching with variables: efficient algorithms and complexity results

zbMATH Keywords

XMLstringstheory of computationimplicationpatterns

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Searching and sorting (68P10)

Cites Work

• The Complexity of Some Problems on Subsequences and Supersequences

Cited In (1)

• Implication of regular expressions

This page was built for publication: Disjoint pattern matching and implication in strings

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