Foundations of software science and computation structures : First International Conference, FoSSaCS '98 held as part of the joint European Conferences on Theory and Practice of Software, ETAPS '98, Lisbon, Portugal, March 28-April 4, 1998 : proceedings

This Book Constitutes The Refereed Proceedings Of The First International Conference On The Foundations Of Software Science And Computation Structures, Fossacs'98, Held As Part Of The Joint European Conferences On Theory And Practice Of Software, Etaps'98, In Lisbon, Portugal, In March/april 1998. The 19 Revised Full Papers Presented In The Book Were Carefully Selected From A Total Of 44 Submissions. Among The Topics Covered Are Formal Specification, Automata Theory, Term Rewriting And Rewriting Systems, Process Algebras, Formal Language Theory, Type Theory, Event Structures, And Iteration Theory. Generalizing Domain Theory / Michael Mislove -- A Cook's Tour Of Equational Axiomatizations For Prefix Iteration / Luca Aceto, Wan Fokkink, And Anna Ingólfsdóttir -- The While Hierarchy Of Program Schemes Is Infinite / Can Adam Albayrak And Thomas Noll -- Analysis Of A Guard Condition In Type Theory / Roberto M. Amadio And Solange Coupet-grimal -- An Event Structure Semantics Of P/t Contextual Nets : Asymmetric Event Structures / Paolo Baldan, Andrea Corradini, And Ugo Montanari -- Pumping Lemmas For Timed Automata / Danièle Beauquier -- Asynchronous Observations Of Processes / Michele Boreale, Rocco De Nicola, And Rosario Pugliese -- Minor Searching, Normal Forms Of Graph Relabelling : Two Applications Based On Enumerations By Graph Relabelling / Anne Bottreau And Yves Métivier -- Partial Metrics And Co-continuous Valuations / Michael A. Bukatin And Svetlana Yu. Shorina -- Mobile Ambients / Luca Cardelli And Andrew D. Gordon -- Rational Term Rewriting / Andrea Corradini And Fabio Gadducci -- The Appearance Of Big Integers In Exact Real Arithmetic Based On Linear Fractional Transformations / Reinhold Heckmann -- Net Refinement By Pullback Rewriting / Renate Klempien-hinrichs -- On Piecewise Testable, Starfree, And Recognizable Picture Languages / Oliver Matz -- Functor Categories And Two-level Languages / Eugenio Moggi -- Deciding Properties For Message Sequence Charts / Anca Muscholl, Doron Peled, And Zhendong Su -- The Church-rosser Languages Are The Deterministic Variants Of The Growing Context-sensitive Languages / Gundula Niemann And Friedrich Otto -- Deterministic Rational Transducers And Random Sequences / Sylvain Porrot [and Others] -- Resource Based Models For Asynchrony / Julian Rathke. Maurice Nivat (ed.). Includes Bibliographical References And Index. Generalizing domain theory....Pages 1-19 A cook's tour of equational axiomatizations for prefix iteration....Pages 20-34 The WHILE hierarchy of program schemes is infinite....Pages 35-47 Analysis of a guard condition in type theory....Pages 48-62 An event structure semantics for P/T contextual nets: Asymmetric event structures....Pages 63-80 Pumping Lemmas for timed automata....Pages 81-94 Asynchronous Observations of Processes....Pages 95-109 Minor searching, normal forms of graph relabelling: Two applications based on enumerations by graph relabelling....Pages 110-124 Partial metrics and co-continuous valuations....Pages 125-139 Mobile ambients....Pages 140-155 Rational term rewriting....Pages 156-171 The appearance of big integers in exact real arithmetic based on Linear Fractional Transformations....Pages 172-188 Net refinement by pullback rewriting....Pages 189-202 On piecewise testable, starfree, and recognizable picture languages....Pages 203-210 Functor categories and two-level languages....Pages 211-225 Deciding properties for message sequence charts....Pages 226-242 The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages....Pages 243-257 Deterministic rational transducers and random sequences....Pages 258-272 Resource based models for asynchrony....Pages 273-287 The 19 papers presented in this volume were selected from a total of 44 submissions. Among the topics covered are: formal specification; automata theory; term rewriting and rewriting systems; process algebras; formal language theory; type theory; event structures; and iteration theory.