154 research outputs found
Petri Net Languages and Infinite Subsets of Nm
No full textAbstractFamilies of Petri net languages are usually defined by varying the type of transition labeling and the class of subsets of Nm to be used as sets of final markings (m is the number of places). So far three main classes of subsets have been studied: the trivial class containing as single element Nm, the class of finite subsets of Nm, and the class of ideals (or covering subsets) of Nm. In this paper we extend the known hierarchy of Petri net languages by considering the classes of semi-cylindrical, star-free, recognizable, rational (or semilinear) subsets of Nm. We compare the related Petri net languages. For arbitrarily labeled and for λ-free labeled Petri net languages, the above hierarchy collapses: one does not increase the generality by considering semilinear accepting sets instead of the usual finite ones. However, for free-labeled and for deterministic Petri net languages, we show that one gets new distinct subclasses of languages, for which several decidability problems become solvable. We establish as intermediate results some properties of star-free subsets of general monoids
Nonlinear perron-probenius theory and dynamics of cone maps
No full textIn this paper several recent results concerning the dynamics of order preserving (sub) homogeneous maps on polyhedral cones are reviewed. These results were obtained by the author in collaboration with Marianne Akian, Stephane Gaubert, Roger Nussbaum, Michael Scheutzow and Colin Sparrow in [2], [13] and [15] and are new nonlinear extensions of the Perron-Frobenius theory
Linear algebra over T-pairs
No full textThis paper treats linear algebra over a semiring pair, in a wide range of
applications to tropical algebra and related areas such as hyperrings and fuzzy
rings. First we present a more general category of ``pairs'' with their
morphisms, called ``weak morphisms,'' paying special attention to supertropical
pairs, hyperpairs, and the doubling functor. Then we turn to matrices and the
question of whether the row rank, column rank, and submatrix rank of a matrix
are equal. Often the submatrix rank is less than or equal to the row rank and
the column rank, but there is a counterexample to equality, discovered some
time ago by the second author, which we provide in a more general setting
(``pairs of the second kind'') that includes the hyperfield of signs.
Additional positive results include a version of Cramer's rule, and we find
situations when equality holds, encompassing results by Akian, Gaubert,
Guterman, Izhakian, Knebusch, and Rowen. We pay special attention to the
question of whether vectors of length need be dependent. At the end,
we introduce a category with stronger morphisms, that preserve a surpassing
relation.Comment: 46 p
Solving multichain stochastic games with mean payoff by policy iteration
No full textInternational audienceZero-sum stochastic games with finite state and action spaces, perfect information, and mean payoff criteria arise in particular from the monotone discretization of mean-payoff pursuit-evasion deterministic differential games. In that case no irreducibility assumption on the Markov chains associated to strategies are satisfied (multichain games). The value of such a game can be characterized by a system of nonlinear equations, involving the mean payoff vector and an auxiliary vector (relative value or bias). Cochet-Terrasson and Gaubert proposed in (C. R. Math. Acad. Sci. Paris, 2006) a policy iteration algorithm relying on a notion of nonlinear spectral projection (Akian and Gaubert, Nonlinear Analysis TMA, 2003), which allows one to avoid cycling in degenerate iterations. We give here a complete presentation of the algorithm, with details of implementation in particular of the nonlinear projection. This has led to the software PIGAMES and allowed us to present numerical results on pursuit-evasion games
Iteration of order preserving subhomogeneous maps on a cone
No full textWe investigate the iterative behaviour of continuous order preserving subhomogeneous maps , where is a polyhedral cone in a finite dimensional vector space. We show that each bounded orbit of converges to a periodic orbit and, moreover, the period of each periodic point of is bounded by where is the number of facets of the polyhedral cone. By constructing examples on the standard positive cone in , we show that the upper bound is asymptotically sharp
Tropical Cramer Determinants Revisited
No full textSee also arXiv:1309.6298International audienceWe prove general Cramer type theorems for linear systems over various extensions of the tropical semiring, in which tropical numbers are enriched with an information of multiplicity, sign, or argument. We obtain existence or uniqueness results, which extend or refine earlier results of Gondran and Minoux (1978), Plus (1990), Gaubert (1992), Richter-Gebert, Sturmfels and Theobald (2005) and Izhakian and Rowen (2009). Computational issues are also discussed; in particular, some of our proofs lead to Jacobi and Gauss-Seidel type algorithms to solve linear systems in suitably extended tropical semirings
Analysis of the Deuxieme Sonate pour flute t piano composer Philippe Gaubert and contextualization of his work
No full textEn este trabajo se hace el análisis de la Segunda Sonata de Philippe Gaubert, describiendo los elementos musicales y morfológicos que la componen, rescatando el origen de la forma sonata y haciendo una descripción de las estructuras melódicas rítmicas y armónicas en las cuales se desarrolla esta obra. También se describen y valoran los aspectos contextuales de la música francesa a partir de 1870, de los principales y más representativos compositores vinculados al repertorio de la música francesa emergente entre los siglos XIX y XX, y cómo el maestro Philippe Gaubert, se encuentra relacionado con el repertorio de la música de la tradición francesa, siendo uno de los más representativos y destacados compositores en París. El contexto del autor se complementa con la elaboración de un catálogo de música de cámara de los compositores de los periodos Romántico y Moderno, incluyendo el formato de flauta traversa y pianoforte, pues este gran repertorio está consagrado al archivo de piezas para música de cámara y al estudio de la flauta traversa moderna.In this project the analysis of the Second Sonata of Philippe Gaubert is made, describing the musical and morphological elements that compose it, rescuing the origin of sonata form and by a description of the rhythmic, harmonic and melodic in which structures this piece develops it. Also describes and value the contextual aspects of French music from 1870, the main and most representative composers linked to the repertoire of the emerging French music from the nineteenth and twentieth centuries, and how the composer Philippe Gaubert is related to the repertoire and of the French tradition, he who was of the most representative and prominent composers in Paris. The context of the author is complemented by the elaboration of a catalog of chamber music the composers of the periods Romantic and Modern, including the format for flute and pianoforte, this includes a repertoire is dedicated to file pieces for chamber music and the study of modern flute.universidad Distrita
De la convexité tropicale aux jeux à somme nulle
No full textConférence plénièreInternational audienc
Rational Series over Dioids and Discrete Event Systems
No full textthis paper is obviously too short for such a program, we have chosen to propose an introductive guided tour. A more detailed exposition will be found in our references and in a more complete paper to appear elsewhere. 1 Rational Series in a Single Indeterminat
Tropical convexity and its applications to zero-sum games
No full textMini-course (3h)National audienc
- …
