NetNews Usenet Archive 1992 #19

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / doc / techrepo / 145 < prev next >

Wrap

Internet Message Format | 1992-09-02 | 28.6 KB

Path: sparky!uunet!olivea!hal.com!darkstar.UCSC.EDU!golding From: Marie-Helene.Comte@sophia.inria.fr (Marie-Helene Comte) Newsgroups: comp.doc.techreports Subject: INRIA Sophia Antipolis TR list Message-ID: <1832r8INNdun@darkstar.UCSC.EDU> Date: 27 Aug 92 13:14:05 GMT Organization: University of California, Santa Cruz Lines: 557 Approved: compdoc-techreports@ftp.cse.ucsc.edu NNTP-Posting-Host: willow.ucsc.edu Originator: golding@willow I N R I A ( National Institute for Research in Computer Science and Automation) Unite de recherche de Sophia Antipolis INRIA-SOPHIA ANTIPOLIS Technical report AUGUST 1992 The following technical reports are available. If you want a paper copy send a email to : doc@sophia.inria.fr You can also obtain by the net the corresponding files: - In DVI format using the wais base: ra-zenon-inria-fr on zenon.inria.fr port 210 - In Postscript format using one of the following: * wais base : ra-mime-zenon-inria-fr on zenon.inria.fr port 210 ( this source is an index of MIME documents containning pointers and requires metamail on the client size) * anonymous FTP on: zenon.inria.fr , directory /pub/rapports and soon on : ftp.inria.fr , directory /INRIA/publication ---------------------------------------------------------------------- RT141 I.Jacobs and L.Rideau : A Centaur tutorial Une introduction au systeme Centaur AUGUST 1992 In english language This paper presents the Centaur system through a tutorial describing the creation of an environment for a small language of mathematical expressions called Exp. With Centaur, the user may interactively generate programming language environments, including structured editors, debuggers, interpreters, and other tools. In this tutorial, all phases of language specification are covered: the design of the abstract and concrete syntax of Exp in Metal and Sdf, the pretty printing rules in Ppml, and the semantics of an Exp interpreter in Typol. The tools generated by Centaur based on these specifications are enhanced by a user interface built with Centaur graphic primitives. Dans ce papier, nous presentons le systeme Centaur qui est un outil interactif de generation d'environnements de langages de programmation, c'est a dire des editeurs structures, des interpretes, et d'autres outils de mise au point. Nous decrivons la creation d'un environnement pour un petit langage d'expressions mathematiques appele Exp. Toutes les etapes de specification du langage sont parcourues: la specification de la syntaxe abstraite et de la syntaxe concrete de Expen Metal et en Sdf, les regles d'affichage en Ppml, et la semantique d'un evaluateur d'expressions en Typol. De plus, les outils generes sont integres dans une interface homme-machine construite a partir des primitives graphiques de Centaur. ---------------------------------------------------------------------- RR1735 F. Campillo, F. Le Gland et Y. Kutoyants : Asymptotics of the GLRT for the disorder problem in diffusion processes Comportement asymptotique du test du rapport de vraisemblance generalise pour la detection de changement dans les diffusion JULY 1992 In english language We consider the problem of detecting a change in the drift coefficient of a diffusion type process (disorder problem), using the generalized likelihood ratio test (GLRT). Assuming that a change has occured, the asymptotic behaviour (consistency, asymptotic probability distribution) of the maximum likelihood estimate of the change time has already been investigated in the small noise asymptotics. The purpose of this paper is to study the asymptotics of the GLRT itself, i.e. the asymptotic behaviour of both the probability of false alarm and theprobability of miss detection. We prove that these probabilities go to zero with exponential rate, provided a simple detectability assumption is satisfied by the limiting deterministic system. We also investigate the robustness of the GLRT with respect to model misspeci fication, which is a very important property for practical implementation. Here, misspecification means that some wrong expressions are used for either the drift coefficient (before change), or the change coefficient. We obtain roughly the same behaviour for the error probabilities, as in the correctly specified case, although the detectability assumption will include the requirement that thechange to be detected is larger in some sense than the misspecification error. Nous considerons le probleme de detecter un changement dans le coefficient de derive d'un processus de diffusion, en utilisant le test du rapport de vraisemblance generalise (GLRT). Sous l'hypothese qu'un changement a eu lieu, le comportement asymptotique (consistance, distribution asymptotique) de l'estimateur du maximum de vraisemblance pour l'instant de changement, a deja ete etudie dans l'asymptotique petit bruit. Le but de cet article est d'etudier le comportement asymptotique du GLRT, c'est-a-dire le comportement des probabilites de fausse alarme et de non-detection. Nous montrons que ces probabilites convergent vers zero avec une vitesse exponentielle, pourvu qu'une hypothese de detectabilite soit verifiee par le systeme deterministe limite. Nous nous interessons aussi a la robustesse du GLRT vis-a-vis de possibles erreurs de modelisation, qui est une propriete tres importante pour l'implementation pratique du test. Les erreurs de modelisation peuvent porter aussi bien sur le coefficient de derive (avant le changement), que sur le coefficient de changement. Nous obtenons le meme type de comportement asymptotique que dans le cas ou le modele est correct, sous l'hypothese supplementaire que le changement a detecter soit plus grand, dans un certain sens, que l'erreur de modelisation. ---------------------------------------------------------------------- RR1731 I.Attali and P.Franchi-Zannettacci : Language-based document processing Manipulation de documents avec le systeme Centaur JULY 1992 In english language This paper proposes an application of programming environments generation to structured documents manipulation. We use Centaur as a formal tool to model and implement logical and physical structure, logical editing and layout processing, document analysis, re-use and conversion for a sample class of documents: scientific articles including equations and figures. To make connections with real document systems, we choose to give two particular external forms to the logical structure: Tioga source and LaTEX source. From the specifications of the logical and physical structures of the Article document class on one hand, and, on the other hand, the specification of the layout processing (viewed as its semantics according to the Tioga or the LaTEX layout model) and other semantic tools, the Centaur system automatically generates structured environments for Tioga and LaTEX documents and conversions between them. ---------------------------------------------------------------------- RR1698 R.B. Devloo, L.Fezoui and S.Lacire : A C+++ interface for programming on the connection machine Une interface C+++ pou programmer sur la connection machine MAY 1992 In french language In this work, a set of C++ classes are described which provide the Connection Machine programmer with a simplified interface to the PARIS library. Numerical test cases such as parallel arithmetic operations (scalar product, SAXPY,..) and a Jacobi iterative resolution, are used to perform a validation of the C++ interface. Performance results of the C++ interface are presented and compared to those obtained using the PARIS library or using high-level langages of the CM-2 system such as C* or CM-FORTRAN. A classical example in numerical ecology is used for illustrating the performance in parallel computation with integers. On decrit ici un ensemble de classes C++, noyau d'une interface a la librairie PARIS de la Connection Machine. Des exemples numeriques simples: operations arithmetiques (produit scalaire, SAXPY, ..) et la resolution d'un systeme lineaire par Jacobi sont utilisees pour valider l'interface. On compare les performances de l'interface C++ avec celles de la librairie C/PARIS ainsi qu'avec celles obtenues en utilisant deux langages evolues de la Connection Machine: C* et CM-FORTRAN. Un cas test classique en ecologie est presente pour illustrer les performances du calcul parallele avec des entiers. ---------------------------------------------------------------------- RR1683 B. Palmerio : Mesh adaptation for compressible flows Methodes de maillages adaptatifs pour des ecoulements compressibles MAY 1992 In english language We describe here some recent developments in mesh adaption for compressible viscous inviscid flow simulation. One of the most challenging task is to capture efficiently thin layers such as boundary layers, mixing layers. Two important issues, the coupling between mesh and flow, and the use of flat elements for stretching are considered in the case of deformation mesh systems. The paper is illustrated by results obtained by INRIA-Rocquencourt, INRIA-Sophia-Antipolis and Dassault-Saint Cloud teams [4,5,28,29], [12,16], [18,22]. On presente une synthese sur les differents methodes et ingredients concernant l'adaption de maillage pour des ecoulements compressibles visqueux ou non. Le but principal est en general de capturer des structures minces telles que couches limites ou couches de melanges. Ce contexte fait apparaitre deux points importants, le couplage maillage-ecoulement et l'usage d'elements plats, que l'on utilise dans le cas de deformations de maillage. Cette presentation est illustree par des travaux realises a l'INRIA-Rocquencourt, a l'INRIA-Sophia-Antipolis et par une equipe de Dassault-Saint Cloud [4,5,28,29], [12,16], [18,22]. ---------------------------------------------------------------------- RR1652 M.C. Ciccoli et J.A. Desideri : Homenthalpic-flow approach for hypersonic inviscid non-equilibrium flows Approche homenthalpique pour les ecoulements hypersoniques reactifs non visqueux APRIL 1992 In english language Two different methods for the numerical simulation of steady, inviscid, non-equilibrium reactive flow governed by Euler equations augmented by a 5-species 17-reaction finite-rate dissociation model are studied. The employed approximations are based on a conservative mixed Finite-Volume/Finite-Element upwind formulation. The study concentrates on the efficiency of the pseudo-time integration methods as iterative algorithms. The iterative properties of the basic method are demonstrated by various computations of flow fields around blunt bodies. In particular, the effect of varying the global Damkholer number (i.e. the size of the geometry) is illustrated. A variant of the basic method is proposed: We know that for steady (external) flows with uniform free-stream, the total enthalpy is constant throughout the domain. Hence, an algorithm which conserves this quantity has been implemented in which the energy equation (in differential form) is not solved but replaced by its (algebraic) first integral. The extension of existing flux-vector splittings (FVS) to this context where one less PDE is solved and one algebraic constraint is enforced, is examined in Section 4 in which the FVS is demonstrated to be proper. Finally, the efficiency of the proposed new approach is assessed by numerical experiments for first and second order approximation schemes. On presente deux methodes numeriques pour la simulation d'ecoulements hypersoniques reactifs non visqueux regis par les equations d'Euler couplees a un modele chimique a 5 especes et 17 reactions. On emploie des approximations spatiales decentrees de type Volumes Finis/Elements Finis. On s'interesse a l'efficacite des algorithmes en temps des deux methodes. Les proprietes iteratives de la methode de base sont illustrees par les calculs d'ecoulements autour de corps arrondis. En particulier, l'effet du nombre de Damkholer (i.e. la taille de la geometrie) est mise en evidence. On propose une variante a la methode de base: On sait que pour les ecoulements externes avec conditions a l'infini uniformes, l'enthalpie totale est constante dans tout le domaine. Nous avons donc mis au point un algorithme qui conserve cette quantite et dans lequel l'equation differentielle de l'energie est remplacee par son integrale premiere (algebrique). Dans la section 4, on a adapte les decompositions de flux existantes a ce contexte et demontre leur validite. Enfin, on presente une experimentation numerique de ce nouvel algorithme au premier et au second ordre en espace. ---------------------------------------------------------------------- RR1638 E. Altman and P.Nain : Closed-loop control with delayed information Controle a boucle fermee avec information retardee MARCH 1992 In english language The theory of Markov Control Model with Perfect State Information (MCM-PSI) requires that the current state of the system is known to the decision maker at decision inst ants. Otherwise, one speaks of Markov Control Model with Imperfect State Information (MCM-ISI). In this article, we introduce a new class of MCM-ISI, where the information on the state of the system is delayed. Such an information structure is encountered, for instance, in high-speed data networks. In the first part of this article, we show that by enlarging the state space so as to include the last known state as well as all the decisions made during the travel time of the information, we may reduce a MCM-ISI to a MCM-PSI. In the second part of this paper, this result is applied to a flow control problem . Considered is a discrete time queueing model with Bernoulli arrivals and geometric services, where the intensity of the arrival stream is controlled. At the beginning of slot t+1, t=0,1,2,..., the decision maker has to select the probability of having one arrival in the current time slot from the set {p1,p2}, $0\leq p_2\leq p_1 \leq 1$, only on the basis of the queue-length and action histories in [0, t]. The aim is to optimize a discounted throughput/delay criterion. We show that there exists an optimal policy of a threshold type, where the threshold is seen to depend on the last action. La theorie des modeles de decision markoviens a information parfaite necessite, comme le nom l'indique, la connaissance parfaite de l'etat du systeme aux instants de decision. On parle de modele markovien a information imparfaite lorsque l'etat courant du systeme n'est pas connu du controleur. Dans cet article, nous introduisons une nouvelle structure d'information imparfaite, ou l'information sur l'etat du reseau parvient en retard au controleur. Une telle structure d'information se rencontre, par exemple, dans les reseaux a haut debit. Nous montrons qu'en elargissant l'espace d'etat de fa\c con a y inclure le dernier etat connu, ainsi que toutes les actions deja prises, on peut reduire un modele a information retardee en un modele a information parfaite. Ce resultat est ensuite applique a un probleme de controle de flux. Plus precisement, nous considerrons un modele de file d'attente discretise ou la loi des temps de service est geometrique et ou l'intensite du flux (Bernoulli) d'arrivee des clients est controlee. A l'instant $t+1$, le controleur choisit dans l'ensemble $\{p_1,p_2\}$, $0\leq p_2\leq p_1 \leq 1$, la probabilite d'une arrivee dans l'intervalle de temps $[t+1,t+2)$. Pour ce faire, il ne connait que l'evolution du nombre de clients dans $[0,t]$ ainsi que toutes les decisions prises dans $[0,t]$. L'objectif est la minimisation d'une fonctionnelle de cout (penalisee) du type ``debit efficace/temps de reponse moyen''. Nous montrons l'existence d'une politique optimale a seuil, ou la valeur du seuil depend de la derniere action. ---------------------------------------------------------------------- RR1637 E.Altman and P.Nain : Optimal control of the M/G/1 queue with repeated vacations of the servers Controle optimal d'une file M/G/1 avec vacances du serveur MARCH 1992 In english language We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Nous presentons dans cet article plusieurs proprietes asymptotiques des processus de decision markoviens avec contraintes et a espace d'etat denombrable. Nous considerons a la fois des criteres de cout penalise et des criteres de cout moyen, ou les couts ne sont pas necessairement bornes. Nous nous interessons successivement a la convergence du probleme a horizon fini vers le probleme a horizon infini, a la convergence du probleme avec un espace d'etat tronque vers le probleme avec un espace d'etat infini et a la convergence du probleme quand le facteur de penalisation tend vers une limite. Pour tous ces cas, nous etablissons la convergence du cout optimal et la convergence de la politique optimale. De plus, a partir de la politique optimale obtenue pour chaque probleme limite, nous construisons une politique qui est quasi optimale pour les autres problemes. ---------------------------------------------------------------------- RR1601 J.P.Cioni, L.Fezoui and H.Steve : Approximation des equations de maxwell par des schemas decentres en elements finis Upwind finite element schemes for solving the maxwell equations FEBRUARY 1992 In french language A Finite-Volume/Finite-Element mixed approach, largely used in CFD, is applied here to solve numerically the time-dependant Maxwell system. The scheme used is third order accurate both in time and space. We are particularly concerned here with the simulation of bidimensionnal scattering problems, in the case of linear material and homogeneous media. Une approximation mixte Elements finis/Volumes finis couramment employee en mecanique des fluides est ici appliquee a la resolution des equations de Maxwell en regime temporel. Le schema utilise est d'ordre trois en temps et en espace. On s'interesse ici plus particulierement a la simulation de problemes de diffraction bidimensionnels en milieu homogene et pour des materiaux lineaires. ---------------------------------------------------------------------- RR1598 E. ALtman : Asymptotic properties of constrained markov decision processes Proprietes asymptotiques des processus de decision markoviens avec contraintes JANUARY 1992 In english language We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Nous presentons dans cet article plusieurs proprietes asymptotiques des processus de decision markoviens avec contraintes et a espace d'etat denombrable. Nous considerons a la fois des criteres de cout penalise et des criteres de cout moyen, ou les couts ne sont pas necessairement bornes. Nous nous interessons successivement a la convergence du probleme a horizon fini vers le probleme a horizon infini, a la convergence du probleme avec un espace d'etat tronque vers le probleme avec un espace d'etat infini et a la convergence du probleme quand le facteur de penalisation tend vers une limite. Pour tous ces cas, nous etablissons la convergence du cout optimal et la convergence de la politique optimale. De plus, a partir de la politique optimale obtenue pour chaque probleme limite, nous construisons une politique qui est quasi optimale pour les autres problemes. ---------------------------------------------------------------------- RR1596 E. Altman, P. Konstantopoulos, and Z. Liu : Some Qualitatives properties in Polling Systems Proprietes Qualitatives de Systemes a Polling FEBRUARY 1992 In english language Consider a polling system with K 1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide sufficient conditions under which the vector of queue lengths is stable. We treat several criterions for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in set-up times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. For polling systems with mixed limited, gated and exhaustive service disciplines and without set-up times, we prove that the weighted sum of mean waiting times increases in the arrival rate, in the first and second moments of the service times and in the variances of the walking times. This monotonicity also holds with respect to the mean walking times if they are deterministic or if there are "many queues" or the system is heavily loaded. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes. Nous considerons un systeme a polling compose de K 1 files d'attente et un seul serveur qui visite les files d'une maniere cyclique. La discipline de service dans chaque file d'attente est de type "gated" general ou exhaustif general. Nous supposons que les arrivees dans chaque file forment un processus de Poisson, et que les temps de service, les temps du deplacement du serveur et les temps du demarrage pde service dans les files sont des sequence i.i.d. de variables aleatoires. Nous fournissons des conditions suffisantes pour que le vecteur des longueurs des files d'attente est stable. Nous traitons plusieurs criteres de stabilite : l'ergodicite du processus, l'ergodicite geometrique, et le taux geometrique de convergence du premier moment. Ces conditions impliquent aussi la convergence faible des temps des stations, des temps d'entrevisites et des temps de cycle. Nous montrons que pour ce systeme a polling, les temps de stations, d'entrevisites, et de cycle, aussi bien en regime transitoire que stationaire, sont stochastiquement croissants en taux d'arrivees, en temps de services, en temps de deplacement du serveur et en temps de demarrage de service. Pour des systemes a polling avec services mixtes, nous demontrons que la somme ponderee des temps d'attente moyens est croissante en taux d'arrivees, en premier et deuxieme moments de temps de services et en variance du temps du deplacement. Cette monotonie tient aussi par rapport au temps moyens de deplacement, a condition que ces temps sont deterministes, ou qu'il y a "beaucoup" de files d'attente, ou bien que le systeme est tres charge. Finalement, nous prouvons que le temps moyen de cycle, le temps moyen d'entrevisites et le temps moyen des station sont invariants sous des disciplines de services generales, et des processus d'arrives et de services stationaires. ----------------------------------------------------------------------- RR1568 E. Altman : Denumerable constrained Markov decision problems and finite approximations Processus de decision markoviens a etats denombrables sous contraintes: theorie et approximations Received DECEMBER 90, revised DECEMBER 91 In english language The purpose of this paper is two fold. First to establish the Theory of discounted constrained Markov Decision Processes with a countable state and action spaces with general multi-chain structure. Second, to introduce finite approximation methods. We define the occupation measures and obtain properties of the set of all achievable occupation measures under the different admissible policies. We establish the optimality of stationary policies for the constrained control problem, and obtain a LP with a countable number of decision variables through which optimal stationary policies are computed. Since for such a LP one cannot expect to find an optimal solution in a finite number of operations, we present two schemes for finite approximations and establish the convergence of optimal values and policies for both the discounted and the expected average cost, with unbounded cost. Sometimes it turns to be easier to solve the problem with infinite state space than the problem with finite yet large state space. Based on the optimal policy for the problem with infinite state space, we construct policies which are almost optimal for the problem with truncated state space. This method is applied to obtain an ffl-optimal policy for a problem of optimal priority assignment under constraints for a system of K finite queues. Nous etablissons d'abord la theorie des processus de decision Markoviens sous contraintes avec un espace denombrable d'etats et d'actions, une structure ergodique generale et un cout penalise. Nous presentons des conditions pour l'existence d'une politique stationnaire optimale, qui peut etre derivee d'une programmation lineaire infinie. Puis, nous introduisons des methodes basees sur la troncature de l'espace d'etat pour approximer la solution du probleme original. ---------------------------------------------------------------------- =========================================================================== Co-moderator: Richard Golding, Computer & Information Sciences, UC Santa Cruz compdoc-techreports-request@ftp.cse.ucsc.edu