Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ucselx!bionet!agate!ucbvax!geocub.greco-prog.FR!courcell From: courcell@geocub.greco-prog.FR (Bruno Courcelle) Newsgroups: comp.theory Subject: Publication announcement - by B. Courcelle and M. Mosbah Message-ID: <9011300937.AA00204@geocub.greco-prog.fr> Date: 30 Nov 90 16:19:57 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Bruno Courcelle Lines: 30 Publication announcement MONADIC SECOND-ORDER EVALUATIONS ON TREE DECOMPOSABLE GRAPHS by B.COURCELLE, M. MOSBAH, Bordeaux -1 University, FRANCE Abstract: We consider mappings on weighted graphs , like minimal length of a Hamiltonian path or minimal weight of a spanning tree, or number of simple paths linking two designated vertices. Another case is the selection of an optimal subgraph as in Bern, Lawler and Wang. We express the mappings by monadic second-order logic: formulas describe sets of sets of vertices or edges satifying appropriate conditions. Then a semiring homomorphism can select the maximal cardinality, or weight, or the cardinality, etc... For all the problems expressible in this way we obtain polynomial and frequently linear algorithms for graphs given with a decomposition tree, or a parse-tree relative to a context-free graph grammar. We extend results by Arnborg Lagergren and Seese (ICALP 88) or Habel, Kreowski and Vogler ( TAPSOFT 89, LNCS 351), and we answer the questions raised in Bern et al.. This work is available as a printed report (51 pages : request to courcell@geocub.greco-prog.fr) or a LATEX file (request to mosbah@geocub.greco-prog.fr) Mailing address: Universite Bordeaux-1, Informatique, 351 Cours de la Liberation, 33405 TALENCE, France.