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]

Trace monoids and heaps of pieces appear in various contexts in combinatorics. They also constitute a model used in computer science to describe the executions of asynchronous systems. The design of a natural probabilistic layer on top of the model has been a long standing challenge. The difficulty comes from the presence of commuting pieces and from the absence of a global clock. In this paper, we introduce and study the class of Bernoulli probability measures that we claim to be the simplest adequate probability measures on infinite traces. For this, we strongly rely on the theory of trace combinatorics with the Möbius polynomial in the key role. These new measures provide a theoretical foundation for the probabilistic study of concurrent systems. [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]

Abstract: We exhibit a Probabilistic Cellular Automaton (PCA) on with a neighborhood of size 2 which is non-ergodic although it has a unique invariant measure. This answers by the negative an old open question on whether uniqueness of the invariant measure implies ergodicity for a PCA. [Copyright &y& Elsevier]

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]

Consider a multiclass stochastic network with state-dependent service rates and arrival rates describing bandwidth-sharing mechanisms as well as admission control and/or load balancing schemes. Given Poisson arrival and exponential service requirements, the number of customers in the network evolves as a multi-dimensional birth-and-death process on a finite subset of ℕ k. We assume that the death (i.e., service) rates and the birth rates depending on the whole state of the system satisfy a local balance condition. This makes the resulting network a Whittle network, and the stochastic process describing the state of the network is reversible with an explicit stationary distribution that is in fact insensitive to the service time distribution. Given routing constraints, we are interested in the optimal performance of such networks. We first construct bounds for generic performance criteria that can be evaluated using recursive procedures, these bounds being attained in the case of a unique arrival process. We then study the case of several arrival processes, focusing in particular on the instance with admission control only. Building on convexity properties, we characterize the optimal policy, and give criteria on the service rates for which our bounds are again attained. [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]

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]

In the current boom of online services, internationally leading companies promote applications that offer their users an interface to interact and collaborate. Recent development in the study of such systems also included: the derivation of product-form formulae for the stationary state under the matching policy "First Come, First Served", a generalization of the compatibility constraints to general, instead of bipartite, graphs, the construction of optimization tools for models under general compatibility constraints. For doing so, the authors obtain remarkable balance equations that are peculiar to the case of abandonment and shade an interesting light toward a generalization of the aforementioned approach of product forms for matching systems. [Extracted from the article]

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]

Abstract: A trace group (monoid) is the quotient of a free group (monoid) by relations of commutation between some pairs of generators. We prove an analog for the trace group of the Möbius inversion formula for the trace monoid (Cartier and Foata, 1969). To cite this article: A. Bouillard, J. Mairesse, C. R. Acad. Sci. Paris, Ser. I 339 (2004). [Copyright &y& Elsevier]

The height of a trace is the height of the corresponding heap of pieces in Viennot''s representation, or equivalently the number of factors in its Cartier–Foata decomposition. Let h(t) and |t| stand respectively for the height and the length of a trace t. We prove that the bivariate commutative series ∑txh(t)y|t| is rational, and we give a finite representation of it. We use the rationality to obtain precise information on the asymptotics of the number of traces of a given height or length. Then, we study the average height of a trace for various probability distributions on traces. For the uniform probability distribution on traces of the same length (resp. of the same height), the asymptotic average height (resp. length) exists and is an algebraic number. To illustrate our results and methods, we consider a couple of examples: the free commutative monoid and the trace monoid whose independence graph is the ladder graph. [Copyright &y& Elsevier]

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]

We study trace theoretic concurrent systems. This setting encompasses safe (1-bounded) Petri nets. We introduce a notion of irreducible concurrent system and we prove the equivalence between irreducibility and a "spectral property". The spectral property states a strict inequality between radii of convergence of certain growth series associated with the system. The proof that we present relies on Analytic combinatorics techniques. The spectral property is the cornerstone of our theory, in a framework where the Perron-Frobenius theory does not apply directly. This restriction is an inherent difficulty in the study of concurrent systems. We apply the spectral property to the probabilistic theory of concurrent systems. We prove on the one hand the uniqueness of the uniform measure, a question left open in a previous paper. On the other hand, we prove that this uniform measure can be realized as a Markov chain of states-and-cliques on a state space that can be precisely characterized. [ABSTRACT FROM AUTHOR]

Information about the 8th International Conference on Stochastic Networks held at Ecole Normale Superieure in Paris, France in June 23-28, 2008 is presented. Topics during the conference include the new stochastic network model structures and new mathematical problems motivated by contemporary developments in wireless networks, Internet, biology, and manufacturing. The conference featured several speakers including D. Aldous, T. Dieker, and S. Foss.

A tropical matrix is a matrix defined over the max-plus semiring. For such matrices, there exist several non-coinciding notions of rank: the row rank, the column rank, the Schein/Barvinok rank, the Kapranov rank, or the tropical rank, among others. In the present paper, we show that there exists a natural notion of ultimate rank for the powers of a tropical matrix, which does not depend on the underlying notion of rank. Furthermore, we provide a simple formula for the ultimate rank of a matrix, which can therefore be computed in polynomial time. Then we turn our attention to finitely generated semigroups of matrices, for which our notion of ultimate rank is generalized naturally. We provide both combinatorial and geometric characterizations of semigroups having maximal ultimate rank. As a consequence, we obtain a polynomial algorithm to decide if the ultimate rank of a finitely generated semigroup is maximal. [ABSTRACT FROM AUTHOR]

Abstract: Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. Furthermore, the proof is constructive. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity. [Copyright &y& Elsevier]

In a live and bounded free choice Petri net, pick a non-conflicting transition. Then there exists a unique reachable marking in which no transition is enabled except the selected one. For a routed live and bounded free choice net, this property is true for any transition of the net. Consider now a live and bounded stochastic routed free choice net, and assume that the routings and the firing times are independent and identically distributed. Using the above results, we prove the existence of asymptotic firing throughputs for all transitions in the net. Furthermore, the vector of the throughputs at the different transitions is explicitly computable up to a multiplicative constant. [Copyright &y& Elsevier]

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]