Sorting with two ordered stacks in series

MD Atkinson; MM Murphy; Nikola Ruskuc

doi:10.1016/S0304-3975(01)00270-5

Sorting with two ordered stacks in series

MD Atkinson, MM Murphy, Nikola Ruskuc

Research output: Other contribution

Abstract

The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function. (C) 2002 Elsevier Science B.V. All rights reserved.

Original language	English
Volume	289
DOIs	https://doi.org/10.1016/S0304-3975(01)00270-5
Publication status	Published - 23 Oct 2002

Keywords

stacks
permutations
forbidden patterns
enumeration
2-STACK-SORTABLE PERMUTATIONS
FORBIDDEN SUBSEQUENCES
PLANAR MAPS
ENUMERATION

Access to Document

10.1016/S0304-3975(01)00270-5

Cite this

@misc{42a971e1675e430aba2a475f83035349,

title = "Sorting with two ordered stacks in series",

abstract = "The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function. (C) 2002 Elsevier Science B.V. All rights reserved.",

keywords = "stacks, permutations, forbidden patterns, enumeration, 2-STACK-SORTABLE PERMUTATIONS, FORBIDDEN SUBSEQUENCES, PLANAR MAPS, ENUMERATION",

author = "MD Atkinson and MM Murphy and Nikola Ruskuc",

note = "Theoret Comput Sci",

year = "2002",

month = oct,

day = "23",

doi = "10.1016/S0304-3975(01)00270-5",

language = "English",

volume = "289",

type = "Other",

}

TY - GEN

T1 - Sorting with two ordered stacks in series

AU - Atkinson, MD

AU - Murphy, MM

AU - Ruskuc, Nikola

N1 - Theoret Comput Sci

PY - 2002/10/23

Y1 - 2002/10/23

N2 - The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function. (C) 2002 Elsevier Science B.V. All rights reserved.

AB - The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function. (C) 2002 Elsevier Science B.V. All rights reserved.

KW - stacks

KW - permutations

KW - forbidden patterns

KW - enumeration

KW - 2-STACK-SORTABLE PERMUTATIONS

KW - FORBIDDEN SUBSEQUENCES

KW - PLANAR MAPS

KW - ENUMERATION

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

UR - http://dx.doi.org/10.1016/S0304-3975(01)00270-5

U2 - 10.1016/S0304-3975(01)00270-5

DO - 10.1016/S0304-3975(01)00270-5

M3 - Other contribution

VL - 289

ER -

Sorting with two ordered stacks in series

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this