Document Open Access Logo

Partial Permutations Comparison, Maintenance and Applications

Authors Avivit Levy , Ely Porat, B. Riva Shalom

PDF
Thumbnail PDF

File

LIPIcs.CPM.2022.10.pdf
  • Filesize: 0.81 MB
  • 17 pages

Document Identifiers

Author Details

Avivit Levy
  • Department of Software Engineering, Shenkar College, Ramat-Gan, Israel
Ely Porat
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel
B. Riva Shalom
  • Department of Software Engineering, Shenkar College, Ramat-Gan, Israel

Acknowledgements

We would like to thank Amihood Amir for his valuable suggestions while reading a former version of the paper.

Cite AsGet BibTex

Avivit Levy, Ely Porat, and B. Riva Shalom. Partial Permutations Comparison, Maintenance and Applications. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CPM.2022.10

Abstract

This paper focuses on the concept of partial permutations and their use in algorithmic tasks. A partial permutation over Σ is a bijection π_{par}: Σ₁↦Σ₂ mapping a subset Σ₁ ⊂ Σ to a subset Σ₂ ⊂ Σ, where |Σ₁| = |Σ₂| (|Σ| denotes the size of a set Σ). Intuitively, two partial permutations agree if their mapping pairs do not form conflicts. This notion, which is formally defined in this paper, enables a consistent as well as informatively rich comparison between partial permutations. We formalize the Partial Permutations Agreement problem (PPA), as follows. Given two sets A₁, A₂ of partial permutations over alphabet Σ, each of size n, output all pairs (π_i, π_j), where π_i ∈ A₁, π_j ∈ A₂ and π_i agrees with π_j. The possibility of having a data structure for efficiently maintaining a dynamic set of partial permutations enabling to retrieve agreement of partial permutations is then studied, giving both negative and positive results. Applying our study enables to point out fruitful versus futile methods for efficient genes sequences comparison in database or automatic color transformation data augmentation technique for image processing through neural networks. It also shows that an efficient solution of strict Parameterized Dictionary Matching with One Gap (PDMOG) over general dictionary alphabets is not likely, unless the Strong Exponential Time Hypothesis (SETH) fails, thus negatively answering an open question posed lately.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Partial permutations
  • Partial words
  • Genes comparison
  • Color transformation
  • Dictionary matching with gaps
  • Parameterized matching
  • SETH hypothesis

Metrics

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

References

  1. A. Abboud, R. Williams, and H. Yu. More applications of the polynomial method to algorithm design. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 218-230, 2015. Google Scholar
  2. A. Amir, T. Kopelowitz, A. Levy, S. Pettie, E. Porat, and B. R. Shalom. Mind the gap! online dictionary matching with one gap. Algorithmica, 81(6):2123-2157, 2019. Google Scholar
  3. A. Amir, T. Kopelowitz, A. Levy, S. Pettie, E. Porat, and B. R. Shalom. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap. In 27th International Symposium on Algorithms and Computation, ISAAC, pages 12:1-12:12, Sydney, Australia, December 12-14, 2016. Google Scholar
  4. A. Amir and A. Levy. String rearrangement metrics: A survey. In Algorithms and Applications, volume 6060 of Lecture Notes in Computer Science, pages 1-33. Springer, 2010. Google Scholar
  5. A. Amir, A. Levy, E. Porat, and B. R. Shalom. Dictionary matching with one gap. In Alexander S. Kulikov, Sergei O. Kuznetsov, and Pavel A. Pevzner, editors, Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings, volume 8486 of Lecture Notes in Computer Science, pages 11-20. Springer, 2014. Google Scholar
  6. A. Amir, A. Levy, E. Porat, and B. R. Shalom. Dictionary matching with a few gaps. Theor. Comput. Sci., 589:34-46, 2015. Google Scholar
  7. A. Amir, A. Levy, E. Porat, and B. R. Shalom. Online recognition of dictionary with one gap. Information and Computation, 275:104633, 2020. Google Scholar
  8. V. Bafna and P. A. Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25:272-289, 1996. Google Scholar
  9. B. S. Baker. A theory of parameterized pattern matching: algorithms and applications. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 71-80, San Diego, CA, USA, May 16-18, 1993. Google Scholar
  10. A. Bergeron and J. Stoye. On the similarity of sets of permutations and its applications to genome comparison. Journal of Computational Biology, 13(7):1340-1354, 2006. Google Scholar
  11. J. Berstel and L. Boasson. Partial words and a theorem of Fine and Wilf. Theoretical Computer Science, 218(1):135-141, 1999. Google Scholar
  12. B. Blakeley, F. Blanchet-Sadri, J. Gunter, and N. Rampersad. Developments in Language Theory, volume 5583 of LNCS, chapter On the Complexity of Deciding Avoidability of Sets of Partial Words, pages 113-124. Springer, 2009. Google Scholar
  13. F. Blanchet-Sadri, N. C. Brownstein, A. Kalcic, J. Palumbo, and T. Weyand. Unavoidable sets of partial words. Theory of Computing Systems, 45(2):381-406, 2009. Google Scholar
  14. A. Burstein and I. Lankham. Restricted patience sorting and barred pattern avoidance. Permutation patterns, 376:233-257, 2010. Google Scholar
  15. T. M. Chan and R. Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1246-1255, 2016. Google Scholar
  16. M. Charikar, P. Indyk, and R. Panigrahy. New algorithms for subset query, partial match, orthogonal range searching, and related problems. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP), pages 451-462, 2002. Google Scholar
  17. A. Claesson, V. Jelínek, E. Jelínková, and S. Kitaev. Pattern avoidance in partial permutations. Electronic Journal of Combinatorics, 18(1), 2011. Google Scholar
  18. R. Cole, L. Gottlieb, and M. Lewenstein. Dictionary matching and indexing with errors and don't cares. In Proceedings of 36 Annual ACM Symposium on Theory of Computing (STOC), pages 91-100, 2004. Google Scholar
  19. T. H. Cormen, C. E. Leiserson, L. R. Rivest, and C. Stein. Introduction to Algorithms, chapter 14.3: Interval Trees, pages 348-353. MIT Press and McGraw-Hill, 3rd edition, 2009. Google Scholar
  20. M. Equi, V. Mäkinen, and A. I. Tomescu. Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. In Proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 12607 of LNCS, pages 608-622, 2021. Google Scholar
  21. B. Esslinger. Cryptography and mathematics, 2011. Google Scholar
  22. V. Halava, T. Harju, and T. Kärki. Square-free partial words. Information Processing Letters, 108(5):290-292, 2008. Google Scholar
  23. V. Halava, T. Harju, T. Kärki, and P. Séébold. Overlap-freeness in infinite partial words. Theoretical Computer Science, 410(8-10):943-948, 2009. Google Scholar
  24. S. Hannenhalli and P. A. Pevzner. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In Proceedings of the 27th annual ACM symposium on the theory of computing, pages 178-187, 1995. Google Scholar
  25. G. Hoppenworth, J. W. Bentley, D.Gibney, and S. V. Thankachan. The fine-grained complexity of median and center string problems under edit distance. In 28th Annual European Symposium on Algorithms, ESA, volume 173 of LIPIcs, pages 61:1-61:19, 2020. Google Scholar
  26. A. G. Howard. Some improvements on deep convolutional neural network based image classification. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. Google Scholar
  27. R. Impagliazzo and R. Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  28. K.Bingmann, P. Gawrychowski, S. Mozes, and O. Weimann. Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). ACM Trans. Algorithms, 16(4):48:1-48:22, 2020. Google Scholar
  29. D. E. Knuth. The Art of Computer Programming, volume 1-3 Boxed Set. Reading, Massachusetts: Addison-Wesley, 2nd edition, 1998. Google Scholar
  30. M. Krishnamurthy, E. S. Seagren, R. Alder, A. W. Bayles, J. Burke, S. Carter, and E. Faskha. How to cheat at securing linux. Syngress Publishing, Inc., Elsevier, Inc., 2008. Google Scholar
  31. C. Y. Ku and I. Leader. An Erdös-Ko-Rado theorem for partial permutations. Discrete Mathematics, 306(1):74-86, 2006. Google Scholar
  32. G. M. Landau, A. Levy, and I. Newman. LCS approximation via embedding into locally non-repetitive strings. Information and Computation, 209(4):705-716, 2011. Google Scholar
  33. K. G. Larsen and R. Williams. Faster online matrix-vector multiplication. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2182-2189, 2017. Google Scholar
  34. P. Leupold. Partial words for DNA coding. In 10th International Meeting on DNA Computing (DNA 10), volume 3384 of LNCS, pages 224-234. Springer-Verlag, Berlin, 2005. Google Scholar
  35. A. Levy and B. R. Shalom. Online parameterized dictionary matching with one gap. Theoretical Computer Science, 845(14):208-229, 2020. Google Scholar
  36. A. Levy and B. R. Shalom. A comparative study of dictionary matching with gaps: Limitations, techniques and challenges. Algorithmica, 84:590-638, 2022. Google Scholar
  37. Y. Li, G. Hu, Y. Wang, T. M. Hospedales, N. M. Robertson, and Y. Yang. DADA: differentiable automatic data augmentation. CoRR, abs/2003.03780, 2020. URL: http://arxiv.org/abs/2003.03780.
  38. W. J. Myrvold and F. Ruskey. Ranking and unranking permutations in linear time. Inf. Process. Lett., 79(6):281-284, 2001. Google Scholar
  39. R. L. Rivest. Analysis of Associative Retrieval Algorithms. PhD thesis, Stanford University, 1974. Google Scholar
  40. B. R. Shalom. Parameterized dictionary matching with one gap. Theoretical Computer Science, 854(1):1-16, 2021. Google Scholar
  41. A. M. Shur and Y. V. Konovalova. On the periods of partial words. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 2136 of LNCS, pages 657-665. Springer-Verlag, 2001. Google Scholar
  42. H. Straubing. A combinatorial proof of the Cayley-Hamilton theorem. Discrete Mathematics, 43(2-3):273-279, 1983. Google Scholar
  43. L. Taylor and G. Nitschke. Improving deep learning with generic data augmentation. In IEEE Symposium Series on Computational Intelligence, SSCI 2018, Bangalore, India, November 18-21, 2018, pages 1542-1547. IEEE, 2018. Google Scholar
  44. V. V. Williams. On some fine-grained quesions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM), pages 3447-3487, 2019. Google Scholar
  45. X. Zhou, A. Amir, C. Guerra, G. M. Landau, and J. Rossignac. EDoP distance between sets of incomplete permutations: Application to bacteria classification based on gene order. Journal of Computational Biology, 25(11):1193-1202, 2018. URL: https://doi.org/10.1089/cmb.2018.0063.
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 Imprint Privacy Contact