Pattern matching for permutations

DOI10.1016/S0020-0190(97)00209-3zbMath1338.68304OpenAlexW2083354900WikidataQ55951981 ScholiaQ55951981MaRDI QIDQ293263

Prosenjit Bose, Jonathan F. Buss, Anna Lubiw

Publication date: 9 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002093?np=y

zbMATH Keywords

algorithms computational complexity permutation pattern matching separable permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (70)

Grass(mannian) trees and forests: Variations of the exponential formula, with applications to the momentum amplituhedron ⋮ Determinantal formulas for SEM expansions of Schubert polynomials ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ On the least exponential growth admitting uncountably many closed permutation classes ⋮ Order-preserving indexing ⋮ Order-preserving pattern matching with \(k\) mismatches ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Unsplittable classes of separable permutations ⋮ Linear-sized independent sets in random cographs and increasing subsequences in separable permutations ⋮ Labelled well-quasi-order for permutation classes ⋮ On the sparseness of the downsets of permutations via their number of separators ⋮ The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size! ⋮ Sorting by shuffling methods and a queue ⋮ The Brownian limit of separable permutations ⋮ Permutations avoiding certain patterns: The case of length 4 and some generalizations ⋮ Sorting with networks of data structures ⋮ On the poset of non-attacking King permutations ⋮ Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem ⋮ Complete edge-colored permutation graphs ⋮ On the distribution of the number of occurrences of an order-preserving pattern of length three in a random permutation ⋮ The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements ⋮ A linear time algorithm for consecutive permutation pattern matching ⋮ Permutations encoding the local shape of level curves of real polynomials via generic projections ⋮ Parity permutation pattern matching ⋮ The infinite limit of separable permutations ⋮ The skew Brownian permuton: A new universality class for random constrained permutations ⋮ Indexing permutations for binary strings ⋮ Product decompositions of the symmetric group induced by separable permutations ⋮ Sub-quadratic time and linear space data structures for permutation matching in binary strings ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ Algorithms for testing occurrences of length 4 patterns in permutations ⋮ An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem ⋮ The Möbius function of separable and decomposable permutations ⋮ Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations ⋮ Unnamed Item ⋮ Operators of equivalent sorting power and related Wilf-equivalences ⋮ On the sub-permutations of pattern avoiding permutations ⋮ Separable \(d\)-permutations and guillotine partitions ⋮ A polyominoes-permutations injection and tree-like convex polyominoes ⋮ On the longest upsequence problem for permutations ⋮ Generalized Coloring of Permutations ⋮ Algorithmic and algebraic aspects of unshuffling permutations ⋮ Unnamed Item ⋮ An algorithm computing combinatorial specifications of permutation classes ⋮ A counterexample regarding labelled well-quasi-ordering ⋮ Separable elements and splittings of Weyl groups ⋮ Parallel algorithms for separable permutations ⋮ On the growth of the Möbius function of permutations ⋮ Finding common structured patterns in linear graphs ⋮ A bijection between permutations and floorplans, and its applications ⋮ On the number of rectangulations of a planar point set ⋮ Unnamed Item ⋮ Constructing separable Arnold snakes of Morse polynomials ⋮ Separable elements in Weyl groups ⋮ A general exhaustive generation algorithm for Gray structures ⋮ Enumeration Schemes for Restricted Permutations ⋮ Finding and counting permutations via CSPs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Multi-Finger Binary Search Trees ⋮ The solution of a conjecture of Stanley and Wilf for all layered patterns ⋮ On the Brownian separable permuton ⋮ Interval posets of permutations ⋮ Unknotted cycles ⋮ Edit distance between unlabeled ordered trees ⋮ Kernelization lower bound for permutation pattern matching ⋮ The feasible regions for consecutive patterns of pattern-avoiding permutations ⋮ Combinatorial generation via permutation languages. I. Fundamentals ⋮ Order-preserving pattern matching indeterminate strings ⋮ On the topology of the permutation pattern poset

Cites Work

This page was built for publication: Pattern matching for permutations