Affordable Access

Publisher Website

Permuting machines and priority queues

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
349
Issue
3
Identifiers
DOI: 10.1016/j.tcs.2005.07.039
Keywords
  • Permutation
  • Pattern
  • Priority Queue
  • Basis

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Priority queues on parallel machines

on Parallel Computing Jan 01, 1999

Priority queues

Jan 01, 1971

Parallel priority queues

on Information Processing Letters Jan 01, 1991
More articles like this..