Pattern matching with address errors: rearrangement distances

DOI10.1016/J.JCSS.2009.03.001MaRDI QIDQ923879zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Yonatan Aumann, G. Benson, Avivit Levy, Ohad Lipsky, Ely Porat, Uzi Vishne, Steven Skiena

Publication date 24 July 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2009.03.001

zbMATH Keywords

address metricsapproximate pattern matchingrearrangement errorsswaps

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
• String rearrangement metrics: a survey
• Approximate string matching with address bit errors
• Approximate String Matching with Address Bit Errors
• Approximate string matching with stuck address bits

Cites work

• A theory of parameterized pattern matching
• An Extension of the String-to-String Correction Problem
• Approximate String Matching with Address Bit Errors
• Dictionary matching and indexing with errors and don't cares
• Efficient string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster algorithms for string matching with k mismatches
• Generalized String Matching
• scientific article; zbMATH DE number 1003303 (Why is no real title available?)
• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 50596 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1303588 (Why is no real title available?)
• scientific article; zbMATH DE number 2038765 (Why is no real title available?)
• scientific article; zbMATH DE number 910911 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Mixing and covering in the symmetric groups
• On the Cost of Interchange Rearrangement in Strings
• Overlap matching.
• Products of conjugacy classes in groups
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• String matching under a general matching relation

Cited in

(11)

• Approximate string matching with address bit errors
• Exploiting pseudo-locality of interchange distance
• Approximate String Matching with Address Bit Errors
• String rearrangement metrics: a survey
• On the hardness of the consensus string problem
• An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications
• Pattern matching in pseudo real-time
• Approximate string matching with stuck address bits
• Exploiting pseudo-locality of interchange distance
• Average parameterization and partial kernelization for computing medians
• Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances

Describes a project that uses

Uses Software

• Mathematica

This page was built for publication: Pattern matching with address errors: rearrangement distances

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