Search

In a model with impatience, observe that the loss rates of perishable classes can be retrieved from I M i and HT ht . Let HT ht be the vector of arrival rates - or probabilities if time is discrete - of the various classes. A matching policy HT ht determines the matches in case of multiple choices. [Extracted from the article]

Let us color the vertices of the grid ℤd or the infinite regular tree 핋d, using a finite number of colors, with the constraint that some predefined pairs of colors are not allowed for adjacent vertices. The set of admissible colorings is called a nearest-neighbor subshift of finite type (SFT). We study 'uniform' probability measures on SFT, with the motivation of having an insight into 'typical' admissible configurations. We recall the known results on uniform measures on SFT on grids and we complete the picture by presenting some contributions to the description of uniform measures on SFT on 핋d. Then we focus on the problem of uniform random sampling of configurations of SFT. We propose a first method based on probabilistic cellular automata, which is valid under some restrictive conditions. Then we concentrate on the case of SFT on ℤ for which we propose several alternative sampling methods. [ABSTRACT FROM AUTHOR]

Let us consider the simplest model of one-dimensional probabilistic cellular automata (PCA). The cells are indexed by the integers, the alphabet is {0, 1}, and all the cells evolve synchronously. The new content of a cell is randomly chosen, independently of the others, according to a distribution depending only on the content of the cell itself and of its right neighbor. There are necessary and sufficient conditions on the four parameters of such a PCA to have a Bernoulli product invariant measure. We study the properties of the random field given by the space-time diagram obtained when iterating the PCA starting from its Bernoulli product invariant measure. It is a non-trivial random field with very weak dependences and nice combinatorial properties. In particular, not only the horizontal lines but also the lines in any other direction consist of i.i.d. random variables. We study extensions of the results to Markovian invariant measures, and to PCA with larger alphabets and neighborhoods. [ABSTRACT FROM AUTHOR]

For a large Markovian model, a 'product form' is an explicit description of the steady-state behaviour which is otherwise generally untractable. Being first introduced in queueing networks, it has been adapted to Markovian Petri nets. Here we address three relevant issues for product-form Petri nets which were left fully or partially open: (1) we provide a sound and complete set of rules for the synthesis; (2) we characterise the exact complexity of classical problems like reachability; (3) we introduce a new subclass for which the normalising constant (a crucial value for product-form expression) can be efficiently computed. [ABSTRACT FROM AUTHOR]

This paper addresses a decision problem highlighted by Grigorchuk, Nekrashevich, and Sushchanskiĭ, namely the finiteness problem for automaton (semi)groups. For semigroups, we give an effective sufficient but not necessary condition for finiteness and, for groups, an effective necessary but not sufficient condition. The efficiency of the new criteria is demonstrated by testing all Mealy automata with small stateset and alphabet. Finally, for groups, we provide a necessary and sufficient condition that does not directly lead to a decision procedure. [ABSTRACT FROM AUTHOR]

Consider a Markovian Petri net with race policy. The marking process has a 'product form' stationary distribution if the probability of viewing a given marking can be decomposed as the product over places of terms depending only on the local marking. First we observe that the Deficiency Zero Theorem of Feinberg, developed for chemical reaction networks, provides a structural and simple sufficient condition for the existence of a product form. In view of this, we study the classical subclass of free-choice nets. Roughly, we show that the only Petri nets of this class which have a product form are the state machines, which can alternatively be viewed as Jackson networks. [ABSTRACT FROM AUTHOR]

Abstract: We address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? We show that the minimal number of registers is the size of the minimal cut on a bi-infinite graph, namely the unfolding of the dependencies in the digital circuit. Furthermore, the construction of such a cut and the corresponding circuit can be done in polynomial time, using a max-flow min-cut result of Orlin for one-periodic bi-infinite graphs. Finally, we show the relation between this construction and the retiming technique introduced by Leiserson and Saxe. [Copyright &y& Elsevier]

We introduce and study a new model: zero-automatic queues. Roughly, zero-automatic queues are characterized by a special buffering mechanism evolving like a random walk on some infinite group or monoid. The salient result is that all stable zero-automatic queues have a product form stationary distribution and a Poisson output process. When considering the two simplest and extremal cases of zero-automatic queues, we recover the simple M/M/1 queue and Gelenbe's G-queue with positive and negative customers. [ABSTRACT FROM AUTHOR]

Let G be a free product of a finite family of finite groups, with the set of generators being formed by the union of the finite groups. We consider a transient nearest-neighbour random walk on G. We give a new proof of the fact that the harmonic measure is a special Markovian measure entirely determined by a finite set of polynomial equations. We show that in several simple cases of interest, the polynomial equations can be explicitly solved to get closed form formulae for the drift. The examples considered are ℤ/2ℤ⋆ ℤ/3ℤ, ℤ/3ℤ⋆ ℤ/3ℤ, ℤ/kℤ⋆ ℤ/kℤ and the Hecke groups ℤ/2ℤ⋆ ℤ/kℤ. We also use these various examples to study Vershik's notion of extremal generators, which is based on the relation between the drift, the entropy and the growth of the group. [ABSTRACT FROM AUTHOR]

We consider the Artin groups of dihedral type I2(k) defined by the presentation Ak = 〈a,b | prod(a,b;k) = prod(b,a;k)〉 where prod(s,t;k) = ststs ..., with k terms in the product on the right-hand side. We prove that the spherical growth series and the geodesic growth series of Ak with respect to the Artin generators {a,b,a-1, b-1} are rational. We provide explicit formulas for the series. [ABSTRACT FROM AUTHOR]

We introduce a remarkable subclass of the class of topical functions, the class of uniformly topical functions, whose dynamical behaviour is investigated. Every uniformly topical endofunction has a spectral vector, related to some special fixed points (possibly at infinity), about which we establish various properties. In the stochastic case, we prove a multiplicative ergodic theorem, asserting that the stochastic spectral vector exists in all cases. [ABSTRACT FROM AUTHOR]

OSCE for evaluating clinical competence still remains limited in France. This study presents the results of the first experimental use of an OSCE as a formative assessment of French general practice trainees. Fifty trainees rotated through a circuit of 15 standardized patient-based OSCE cases. Differences in scores were determined by analysis of variance. Reliability was calculated with the coefficient alpha. Pearson correlations were used to determine the relationship between station scores and overall OSCE score. Written questionnaires based on Likert-type scales were used to measure OSCE feasibility. No difference was found between total session scores. Significant item-total score correlations were found for 12 of the 15 clinical problems. The reliability of the examination was 0.58. Most participants agreed that the clinical situations were realistic, simulated patients were believable and sampling of cases was representative of general practice. These data confirm the feasibility of OSCE in assessing performance of general practice trainees. Optimal training of observers should improve examination reliability. This study warrants further development to confirm its usefulness as a summative assessment tool. [ABSTRACT FROM AUTHOR]