Disjoint pattern matching and implication in strings

DOI10.1016/J.IPL.2009.11.009MaRDI QIDQ990133zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

XMLstringstheory of computationimplicationpatterns

Mathematics Subject Classification ID

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

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

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)