Regular closed sets of permutations

MH Albert; MD Atkinson; Nikola Ruskuc

doi:10.1016/S0304-3975(03)00212-3

Regular closed sets of permutations

MH Albert, MD Atkinson, Nikola Ruskuc

Research output: Contribution to journal › Article › peer-review

25 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 language	English
Pages (from-to)	85-100
Number of pages	16
Journal	Theoretical Computer Science
Volume	306
Issue number	1-3
DOIs	https://doi.org/10.1016/S0304-3975(03)00212-3
Publication status	Published - 5 Sept 2003

Keywords

regular sets
permutations
involvement
TREES

Access to Document

10.1016/S0304-3975(03)00212-3

Cite this

@article{70ab78d9133d4c50ac8f9243b4985e23,

title = "Regular closed sets of permutations",

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.",

keywords = "regular sets, permutations, involvement, TREES",

author = "MH Albert and MD Atkinson and Nikola Ruskuc",

note = "Seminal paper in a specialist journal; new research area.",

year = "2003",

month = sep,

day = "5",

doi = "10.1016/S0304-3975(03)00212-3",

language = "English",

volume = "306",

pages = "85--100",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier Science BV",

number = "1-3",

}

TY - JOUR

T1 - Regular closed sets of permutations

AU - Albert, MH

AU - Atkinson, MD

AU - Ruskuc, Nikola

N1 - Seminal paper in a specialist journal; new research area.

PY - 2003/9/5

Y1 - 2003/9/5

N2 - 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.

AB - 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.

KW - regular sets

KW - permutations

KW - involvement

KW - TREES

UR - http://www.scopus.com/inward/record.url?scp=0041507104&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(03)00212-3

DO - 10.1016/S0304-3975(03)00212-3

M3 - Article

SN - 0304-3975

VL - 306

SP - 85

EP - 100

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

Regular closed sets of permutations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this