Joint Burke's Theorem and RSK Representation for a Queue and a Store
| Autor: | Moez Draief, Jean Mairesse, Neil O'Connell |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2003 |
| Předmět: |
robinson-schensted-knuth algorithm
tandem of queues non-colliding random walks single server queue storage model burke's theorem [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] Mathematics QA1-939 |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AC,..., Iss Proceedings (2003) |
| Druh dokumentu: | article |
| ISSN: | 1365-8050 |
| DOI: | 10.46298/dmtcs.3339 |
| Popis: | Consider the single server queue with an infinite buffer and a FIFO discipline, either of type M/M/1 or Geom/Geom/1. Denote by $\mathcal{A}$ the arrival process and by $s$ the services. Assume the stability condition to be satisfied. Denote by $\mathcal{D}$ the departure process in equilibrium and by $r$ the time spent by the customers at the very back of the queue. We prove that $(\mathcal{D},r)$ has the same law as $(\mathcal{A},s)$ which is an extension of the classical Burke Theorem. In fact, $r$ can be viewed as the departures from a dual storage model. This duality between the two models also appears when studying the transient behavior of a tandem by means of the RSK algorithm: the first and last row of the resulting semi-standard Young tableau are respectively the last instant of departure in the queue and the total number of departures in the store. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|