Finite automata and pattern avoidance in words

DOI10.1016/j.jcta.2004.10.007zbMath1059.05003arXivmath/0309269OpenAlexW2076758603MaRDI QIDQ1775550

Petter Brändén, Toufik Mansour

Publication date: 4 May 2005

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0309269

zbMATH Keywords

Finite automataTransfer matrixBorder-strip tableauxIncreasing patternsPermutation patternsRestricted words

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05) Formal languages and automata (68Q45)

Related Items (16)

Locally convex words and permutations ⋮ On avoiding 1233 ⋮ Unnamed Item ⋮ Pattern avoidance in poset permutations ⋮ Extensions of the linear bound in the Füredi-Hajnal conjecture ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ Pattern avoidance in ordered set partitions and words ⋮ Pattern avoidance in ordered set partitions ⋮ Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations ⋮ An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ Locally restricted compositions over a finite group ⋮ Restricted \(k\)-ary words and functional equations ⋮ Pattern occurrences in \(k\)-ary words revisited: a few new and old observations ⋮ Strongly restricted permutations and tiling with fences ⋮ Stack-sorting for Words

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• D-finite power series
• Resurrecting the asymptotics of linear recurrences
• The solution of a conjecture of Stanley and Wilf for all layered patterns
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Generating functions for generating trees
• Asymptotics of the number of \(k\)-words with an \(l\)-descent
• The patterns of permutations
• Words restricted by patterns with at most 2 distinct letters
• On the number of permutations avoiding a given pattern
• Restricted permutations
• Permutations of a multiset avoiding permutations of length 3
• Inverses of words and the parabolic structure of the symmetric group

This page was built for publication: Finite automata and pattern avoidance in words