Document Open Access Logo

Boxed Permutation Pattern Matching

Authors Mika Amit, Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Hjalte Wedel Vildhøj

PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.20.pdf
  • Filesize: 495 kB
  • 11 pages

Document Identifiers

Author Details

Mika Amit
Philip Bille
Patrick Hagge Cording
Inge Li Gørtz
Hjalte Wedel Vildhøj

Cite As Get BibTex

Mika Amit, Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, and Hjalte Wedel Vildhøj. Boxed Permutation Pattern Matching. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CPM.2016.20

Abstract

Given permutations T and P of length n and m, respectively, the Permutation Pattern Matching problem asks to find all m-length subsequences of T that are order-isomorphic to P. This problem has a wide range of applications but is known to be NP-hard. In this paper, we study the special case, where the goal is to only find the boxed subsequences of T that are order-isomorphic to P. This problem was introduced by Bruner and Lackner who showed that it can be solved in O(n^3) time. Cho et al. [CPM 2015] gave an O(n^2m) time algorithm and improved it to O(n^2 log m). In this paper we present a solution that uses only O(n^2) time. In general, there are instances where the output size is Omega(n^2) and hence our bound is optimal. To achieve our results, we introduce several new ideas including a novel reduction to 2D offline dominance counting. Our algorithm is surprisingly simple and straightforward to implement.

Subject Classification

Keywords
  • Permutation
  • Subsequence
  • Pattern Matching
  • Order Preserving
  • Boxed Mesh Pattern

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. H. Albert, R. E. Aldred, M. D. Atkinson, and D. A. Holton. Algorithms for pattern involvement in permutations. In Algorithms and Computation, pages 355-367. Springer, 2001. Google Scholar
  2. S. Avgustinovich, S. Kitaev, and A. Valyuzhenich. Avoidance of boxed mesh patterns on permutations. Discrete App. Math., 161(1):43-51, 2013. Google Scholar
  3. Eric Babson and Einar Steingrımsson. Generalized permutation patterns and a classification of the mahonian statistics. Sém. Lothar. Combin, 44(B44b):547-548, 2000. Google Scholar
  4. P. Bose, J. F. Buss, and A. Lubiw. Pattern matching for permutations. Inform. Process. Lett., 65(5):277-283, 1998. Google Scholar
  5. M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev. (2+ 2)-free posets, ascent sequences and pattern avoiding permutations. J. Comb. Theory A, 117(7):884-909, 2010. Google Scholar
  6. P. Brändén and A. Claesson. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electron. J. Combin, 18(2):P5, 2011. Google Scholar
  7. M. L. Bruner and M. Lackner. The computational landscape of permutation patterns. CoRR, abs/1301.0340, 2013. Google Scholar
  8. T. M. Chan and M. Pătraşcu. Counting inversions, offline orthogonal range counting, and related problems. In Proc. 21st ACM-SIAM symposium on Discrete Algorithms, pages 161-173. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  9. T. Chhabra and J. Tarhio. Order-preserving matching with filtration. In Experimental Algorithms, pages 307-314. Springer, 2014. Google Scholar
  10. S. Cho, J. C. Na, K. Park, and J. S. Sim. A fast algorithm for order-preserving pattern matching. Inform. Process. Lett., 115(2):397-402, 2015. Google Scholar
  11. S. Cho, J. C. Na, and J. S. Sim. Improved algorithms for the boxed-mesh permutation pattern matching problem. In Proc. 26th CPM, pages 138-148. Springer, 2015. Google Scholar
  12. M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, A. Langiu, S. P. Pissis, J. Radoszewski, W. Rytter, and T. Waleń. Order-preserving incomplete suffix trees and order-preserving indexes. In Proc. 20th SPIRE, pages 84-95. Springer, 2013. Google Scholar
  13. S. Faro and M. O. Külekci. Efficient algorithms for the order preserving pattern matching problem. CoRR, abs/1501.04001, 2015. Google Scholar
  14. Michael Fredman and Michael Saks. The Cell Probe Complexity of Dynamic Data Structures. In Proc. 21st STOC, pages 345-354. ACM, 1989. Google Scholar
  15. P. Gawrychowski and P. Uznański. Order-preserving pattern matching with k mismatches. In Proc. 25th CPM, pages 130-139. Springer, 2014. Google Scholar
  16. L. Ibarra. Finding pattern matchings for permutations. Inform. Process. Lett., 61(6):293-295, 1997. Google Scholar
  17. J. Kim, A. Amir, J. C. Na, K. Park, and J. S. Sim. On representations of ternary order relations in numeric strings. In Proc. 2nd ICABD, pages 46-52, 2014. Google Scholar
  18. J. Kim, P. Eades, R. Fleischer, S. H. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, and T. Tokuyama. Order-preserving matching. Theoret. Comput. Sci., 525:68-79, 2014. Google Scholar
  19. S. Kitaev. Patterns in permutations and words. Springer Science &Business Media, 2011. Google Scholar
  20. M. Kubica, T. Kulczyński, J. Radoszewski, W. Rytter, and T. Waleń. A linear time algorithm for consecutive permutation pattern matching. Inform. Process. Lett., 113(12):430-433, 2013. Google Scholar
  21. M. Pătraşcu and M. Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In Proc. 55th FOCS, pages 166-175. IEEE, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact