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 |
CORE (COnnecting REpositories)
CORE (COnnecting REpositories)