From: Marie-Helene.Comte@sophia.inria.fr (Marie-Helene Comte)
Newsgroups: comp.doc.techreports
Subject: INRIA Sophia Antipolis TR list
Date: 27 Aug 92 13:14:05 GMT
Organization: University of California, Santa Cruz
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