Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334258 | Theoretical Computer Science | 2005 | 9 Pages |
Abstract
Machines whose sole function is to re-order their input data are considered. Every such machine defines a set of allowable input-output pairs of permutations. These sets are studied in terms of the minimal disallowed pairs (the basis). Some allowable sets with small bases are considered including the one defined by a priority queue machine. For more complex machines defined by two or more priority queues in series or parallel, the basis is proved to be infinite.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
R.E.L. Aldred, M.D. Atkinson, H.P. van Ditmarsch, C.C. Handley, D.A. Holton, D.J. McCaughan,