Computing permutations with double-ended queues, parallel stacks and parallel queues
Computing permutations with double-ended queues, parallel stacks and parallel queues
复制标题
使用双端队列、并行堆栈和并行队列计算排列
DOI：
10.1145/800125.804058
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
V. Pratt
中科院分区：
文献类型：
--
作者：
V. Pratt
存储器可以看作是一台具有输入、输出和存储功能的计算机，但没有明确的功能。唯一可能的输出是其输入的多集合的排列。因此，对一类记忆的自然问题是，它的成员可以计算什么排列？这里我们特别感兴趣的是Knuth [1968]、Even和Itai [1971]以及Tarjan [1972]研究的开关站网络，其中的排列是输入集的排列，而不是输入的多集排列。
A memory may be regarded as a computer with input, output and storage facilities, but with no explicit functional capability. The only possible outputs are permutations of a multiset of its inputs. Thus the natural question to ask of a class of memories is, what permutations can its members compute? We are particularly interested here in switchyard networks studied by Knuth [1968], Even and Itai [1971], and Tarjan [1972], where the permutations are of the set of inputs, rather than of a multiset of them.