Regular closed sets of permutations

MH Albert, MD Atkinson, Nikola Ruskuc

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)

Abstract

Machines whose main purpose is to permute and sort data are studied. The sets of permutations that can arise are analysed by means of finite automata and avoided pattern techniques. Conditions are given for these sets to be enumerated by rational generating functions. As a consequence we give the first non-trivial examples of pattern closed sets of permutations all of whose closed subclasses have rational generating functions. (C) 2003 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)85-100
Number of pages16
JournalTheoretical Computer Science
Volume306
Issue number1-3
DOIs
Publication statusPublished - 5 Sept 2003

Keywords

  • regular sets
  • permutations
  • involvement
  • TREES

Fingerprint

Dive into the research topics of 'Regular closed sets of permutations'. Together they form a unique fingerprint.

Cite this