Permutations Sorted by a Finite and an infinite stack in series

Elder, M; Goh, YK

Permutations Sorted by a Finite and an infinite stack in series

Elder, M

Goh, YK

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2018, 10792 LNCS pp. 220 - 231
Issue Date:: 2018-01-01

Closed Access

	Filename	Description	Size
	main.pdf	Accepted Manuscript version	289.11 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Goh, YK	en_US
dc.date.issued	2018-01-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2018, 10792 LNCS pp. 220 - 231	en_US
dc.identifier.isbn	9783319773124	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/123684
dc.description.abstract	© Springer International Publishing AG, part of Springer Nature 2018. We prove that the set of permutations sorted by a stack of depth t ≥ 3 and an infinite stack in series has infinite basis, by constructing an infinite antichain. This answers an open question on identifying the point at which, in a sorting process with two stacks in series, the basis changes from finite to infinite.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP160100486
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-319-77313-1_17	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Permutations Sorted by a Finite and an infinite stack in series	en_US
dc.type	Conference Proceeding
utslib.citation.volume	10792 LNCS	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	10792 LNCS	en_US

Abstract:

© Springer International Publishing AG, part of Springer Nature 2018. We prove that the set of permutations sorted by a stack of depth t ≥ 3 and an infinite stack in series has infinite basis, by constructing an infinite antichain. This answers an open question on identifying the point at which, in a sorting process with two stacks in series, the basis changes from finite to infinite.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/123684