Results 141 to 150 of about 417 (162)
Some of the next articles are maybe not open access.
Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79, 1979
It is shown that concatenable double-ended queues can be simulated in real-time by double-ended queues without concatenation. Consequently, every multihead Turing machine with head-to-head jumps can be simulated in real-time by multitape Turing machines.
exaly +2 more sources
It is shown that concatenable double-ended queues can be simulated in real-time by double-ended queues without concatenation. Consequently, every multihead Turing machine with head-to-head jumps can be simulated in real-time by multitape Turing machines.
exaly +2 more sources
Computing permutations with double-ended queues, parallel stacks and parallel queues
Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73, 1973A 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?
exaly +2 more sources
An Unbounded Nonblocking Double-Ended Queue
2016 45th International Conference on Parallel Processing (ICPP), 2016We introduce a new algorithm for an unbounded concurrent double-ended queue (deque). Like the bounded deque of Herlihy, Luchangco, and Moir on which it is based, the new algorithm is simple and obstruction free, has no pathological long-latency scenarios, avoids interference between operations at opposite ends, and requires no special hardware support ...
Matthew Graichen +2 more
openaire +1 more source
Simulation model for extended double-ended queueing
Computers & Industrial Engineering, 2010The purpose of this paper is to extend traditional double-ended queuing models using a simulation approach. Traditional double-ended queuing models assume that one supply queue should satisfy one demand queue through instantaneous pairing. Inter-arrival time is assumed to follow an exponential distribution, with arrivals to the system assumed to occur ...
Won Kyung Kim +3 more
openaire +1 more source
Equilibrium Strategies and Optimal Control for a Double-Ended Queue
Asia-Pacific Journal of Operational Research, 2016In this paper, we study a passenger–taxi matching queue system. The system is modeled as a birth-and-death process. Since the system is so complex, we mainly focus on numerical analysis. A centralized system and a decentralized one are considered. In the centralized system, the government sets thresholds for both passengers and taxis to maximize the ...
Ying Shi, Zhaotong Lian
openaire +2 more sources
Obstruction-free synchronization: double-ended queues as an example
23rd International Conference on Distributed Computing Systems, 2003. Proceedings., 2004We introduce obstruction-freedom, a new nonblocking property for shared data structure implementations. This property is strong enough to avoid the problems associated with locks, but it is weaker than previous nonblocking properties-specifically lock-freedom and wait-freedom-allowing greater flexibility in the design of efficient implementations ...
Maurice Herlihy +2 more
openaire +1 more source
Transient behaviour of a double ended Markovian queue
Stochastic Analysis and Applications, 1991This paper studies the transient behaviour of a double–ended Markovian queueing system with finite waiting space. The transition probabilities and other queueing parameters have been obtained in a simple closed form using matrix ...
O.P. Sharma, N.S.K. Nair
openaire +1 more source
Strategic behavior and social optimization in a double-ended queue with gated policy
Computers & Industrial Engineering, 2017Abstract This paper is concerned with a double-ended queueing system which is motivated by the passenger-taxi problem under a gated policy. This policy makes taxis start to balk when the taxi queue length reaches an upper limit and to join again when the taxi queue length is reduced to a lower limit.
Fang Wang +2 more
openaire +1 more source
Further results for the double ended queue
Metrika, 1967For the double ended queue involving taxis and customers at a taxi-stand (Kashyap, 1965 a; b) the probabilities that (i) only taxis are waiting and (ii) only customers are waiting have been investigated by the use of Laplace transform. The L.T.s of the mean queue lengths of taxis and of customers are also obtained.
openaire +1 more source