Albert, Michael; Brignall, Robert; Ruskuc, Nik and Vatter, Vincent
(2019).
![]() |
(Accepted Manuscript)
Due to publisher licensing restrictions, this file is not available for public download until 5 February 2020 Click here to request a copy from the OU Author. |
DOI (Digital Object Identifier) Link: | https://doi.org/10.1016/j.ejc.2019.01.001 |
---|---|
Google Scholar: | Look up in Google Scholar |
Abstract
We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.
Item Type: | Journal Item |
---|---|
Copyright Holders: | 2019 Elsevier |
ISSN: | 0195-6698 |
Academic Unit/School: | Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics Faculty of Science, Technology, Engineering and Mathematics (STEM) |
Item ID: | 59056 |
Depositing User: | Robert Brignall |
Date Deposited: | 11 Feb 2019 08:48 |
Last Modified: | 08 Dec 2019 01:27 |
URI: | http://oro.open.ac.uk/id/eprint/59056 |
Share this page: | ![]() ![]() ![]() ![]() |
Metrics
Altmetrics from Altmetric | Citations from Dimensions |