From owner-reliable_computing Fri May 1 12:26:57 1998 Received: by interval.usl.edu id AA08517 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 1 May 1998 12:26:57 -0500 Received: from frank.cs.bham.ac.uk by interval.usl.edu with SMTP id AA08511 (5.65c/IDA-1.4.4 for ); Fri, 1 May 1998 12:26:16 -0500 Received: from tilly.cs.bham.ac.uk (actually host tilly) by frank.cs.bham.ac.uk with SMTP (MMTA); Fri, 1 May 1998 18:23:36 +0100 Received: by tilly.cs.bham.ac.uk (4.1/client/1.2) id AA01090; Fri, 1 May 98 18:26:03 BST Date: Fri, 1 May 98 18:26:03 BST From: M.Z.Kwiatkowska [at] cs [dot] bham.ac.uk Message-Id: <1090.9805011726 [at] tilly [dot] cs.bham.ac.uk> To: amast [at] cs [dot] utwente.nl, reliable_computing [at] interval [dot] usl.edu Subject: PROBMIV'98: Call for Participation Cc: M.Z.Kwiatkowska [at] cs [dot] bham.ac.uk Sender: owner-reliable_computing Precedence: bulk [Please circulate this to anyone interested. Apologies for multiple copies.] _____________________________________________________________________ Call For Participation Pre-LICS'98 Workshop on PROBABILISTIC METHODS IN VERIFICATION (PROBMIV'98) June 19-20, 1998 Indianapolis, Indiana, USA Sponsored by BRIMS, Hewlett-Packard For up-to-date programme information see URLs: http://www.cs.bham.ac.uk/~mzk/probmiv98.html, mirrored at http://www.cis.ksu.edu/~huth/probmiv98.html and for ALL registration the LICS98 URL: http://lics98.cs.indiana.edu/ _____________________________________________________________________ WORKSHOP DESCRIPTION AND AIMS ============================= SCIENTIFIC JUSTIFICATION: While there has been a steady current of research activity in probabilistic logics and systems for some years, little experimental work has been done up until now. This situation is beginning to change. Randomization has proved effective in deriving efficient distributed algorithms and is now widely used in practical applications, to mention computer networks and graphics. However, randomized algorithms are notoriously difficult to verify: the proofs of their correctness are complex, and therefore argued informally, and thus appropriate formal methods and tools are called for. These have to combine a variety of dissimilar techniques, from conventional proof theory and model checking, through systems modelling to linear algebra and probability theory. The importance of probabilistic verification lies in the fact that it can provide guarantees that the specifications hold with satisfactory probability in cases when conventional model checking fails, for example when exhaustive search is not feasible due to the size of the system, or when checking `soft deadlines' in real-time systems. It can also be useful in average-case analysis of software and as an abstraction technique. The central idea for this workshop is to gather researchers working across the whole spectrum of the research activity in probabilistic verification, from semantics and (computational) linear algebra, through randomized algorithms, probabilistic and fuzzy logics, abstract interpretation, to practical experimental work, tools and applications. The workshop's aim is to enable cross-fertilisation of ideas and techniques between areas that are usually not in regular contact through conferences, while at the same time involving research topics of major concern to the LICS community. FORMAT AND AGENDA: The workshop will be informal and will focus on exchange of information and discussion. It will consist of a number of invited talks on a range of key topics, evenly balanced between theory and applied research, together with a panel session and a number of accepted papers. PROCEEDINGS: Preliminary proceedings will be available at the workshop. An ENTCS volume will be published after the workshop. Submissions by the deadline of 30th August are open to all participants. _____________________________________________________________________ INVITED TALKS ============= Rajeev Alur, University of Pennsylvania. Model checking of probabilistic real-time systems Luca de Alfaro, Tom Henzinger and Orna Kupferman, University of California at Berkeley. Probabilistic issues in the reachability analysis of open systems Christel Baier, Universitat Mannheim, and Vicky Hartonas-Garmhausen, CMU. Probabilistic Verus: semantic foundations and practical results Jeremy Gunawardena, BRIMS, Hewlett-Packard. Timing analysis, dynamical systems and exotic linear algebra Marek Karpinski, University of Bonn. Randomized OBDDs and the model checking Annabelle McIver, Oxford University. Reasoning about efficiency within a probabilistic mu-calculus Prakash Panangaden, McGill University. Stochastic techniques in concurrency Roberto Segala, University of Bologna. Verification of randomized distributed algorithms K Narayan Kumar, Scott Smolka, SUNY Stony Brook, and Rance Cleaveland, North Carolina SU. Infinite Probabilistic and Nonprobabilistic Testing Moshe Vardi, Rice University. An Automata-Theoretic Approach to Probabilistic Verification PANEL SESSION ============= Ed Clarke, CMU, Panel Chair What tools and theory are needed in order to make probabilistic verification practical? ACCEPTED PAPERS =============== Christel Baier, University of Mannheim, Marta Kwiatkowska and Gethin Norman, University of Birmingham. Computing Probability Lower and Upper Bounds for LTL Formulae over Sequential and Concurrent Markov Chains Pedro D'Argenio, Holger Hermanns and Joost-Pieter Katoen, University of Erlangen-Nuernberg. On Asynchronous Generative Parallel Composition Carlos Gregorio-Rodriguez and Manuel Nunez, Universidad Complutense de Madrid. Denotational Semantics for Probabilistic Refusal Testing Klaus Keimel, Technical University of Darmstadt. Semantic Foundation of the Probabilistic Power Domain Christoph Meinel and Harald Sack, Universitaet Trier. Parity-OBDDs - a BDD Structure for Probabilistic Verification Anna Philippou, University of Pennsylvania, Oleg Sokolsky, CCCC, Insup Lee, University of Pennsylvania, Rance Cleaveland, North Carolina, and Scott Smolka, SUNY at Stony Brook. Specifying Failures and Recoveries in PACSR SHORT PRESENTATIONS =================== Jerry den Hartog and Erik de Vink, Vrije Universiteit Amsterdam. Mixing Up Nondeterminism and Probability: a preliminary report Ali Movaghar, Sharif University of Technology. On modeling and analysis of concurrency _____________________________________________________________________ IMPORTANT DATES =============== 8 May 1998 Early registration deadline (LICS) 15 May 1998 Early registration deadline (PROBMIV) 20 May 1998 Papers for preliminary proceedings due 19-20 June 1998 Workshop dates 30 August 1998 Final versions due for the ENTCS volume (submission open to all participants) _____________________________________________________________________ REGISTRATION AND LOCAL INFORMATION ================================== The workshop will take place on June 19-20 1998, just before LICS98 which is on June 21-24. The venue for both PROBMIV98 and LICS98 is University Center, Indiana University, Indianapolis, USA. ALL registration is handled through the LICS98 office, see URL http://lics98.cs.indiana.edu/ Please note that the number of hotel rooms for workshop nights is limited and early booking is advisable. Early registration for LICS ends 8th May, and for pre-LICS workshops 15th May. _____________________________________________________________________ ORGANISING COMMITTEE AND PROGRAM CHAIRS ======================================= Marta Kwiatkowska (Chair) Michael Huth (Co-chair) School of Computer Science Dept of Computing and University of Birmingham Information Sciences Edgbaston, B15 2TT, UK Kansas State University +44 (121) 414-7264 (voice) Manhattan, Kansas 66506, USA +44 (121) 414-4281 (fax) +1 (785) 532-6350 (voice) mzk [at] cs [dot] bham.ac.uk +1 (785) 532-7353 (fax) huth [at] cis [dot] ksu.edu Christel Baier Mark Ryan Dept of Mathematics and School of Computer Science Computer Science University of Birmingham University of Mannheim Edgbaston, B15 2TT, UK Seminargebaude A5 +44 (121) 414-7361 (voice) D-68131 Mannheim, Germany +44 (121) 414-4281 (fax) +49 (621) 292-5094 (voice) mdr [at] cs [dot] bham.ac.uk +49 (621) 292-5364 (fax) baier [at] pi1 [dot] informatik.uni-mannheim.de _____________________________________________________________________ From owner-reliable_computing Tue May 5 04:07:17 1998 Received: by interval.usl.edu id AA14626 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 5 May 1998 11:07:40 -0500 Received: from cs.utep.edu by interval.usl.edu with SMTP id AA14620 (5.65c/IDA-1.4.4 for ); Tue, 5 May 1998 11:07:35 -0500 Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1) id AA26156; Tue, 5 May 98 10:07:17 MDT Date: Tue, 5 May 98 10:07:17 MDT From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich) Message-Id: <9805051607.AA26156 [at] cs [dot] utep.edu> To: reliable_computing [at] interval [dot] usl.edu Subject: International Conference Interval'98 Cc: nhphuong [at] bdvn [dot] vnmail.vnd.net, mkosh [at] cs [dot] utep.edu, interval [at] cs [dot] utep.edu Sender: owner-reliable_computing Precedence: bulk INTERVAL'98, the fourth in a series of biannually organized conferences, was held in Nanjing, China, April 20-23. It was attended by more than 30 researchers from 15 different countries all over the world. The conference was organized by: * Department of Mathematics, Nanjing University * The Editorial Board of the International Journal "Reliable Computing" Whereas the previous meetings focused on relationships of interval mathematics to other areas, Interval, 98 having global optimization as an application area in mind, put strong emphasis on traditional interval methods. New results on well established methods were presented, and complexity issues were discussed. Several talks dealt with new, efficient implementation techniques. Nevertheless, a number of interesting and surprising applications were suggested. Take the foundations of physics or a combination of Western and Oriental medicine as some striking examples. All in all, there were 31 talks. The refereed proceedings of the conference will be published as a special issue of the "Reliable Computing" journal. The conference took place in the relaxed atmosphere of the Holiday Inn Hotel and was supported by the national Natural Science Foundation of China and Nanjing University. The German Research Association (DFG) supported some of the German participants. Due to the facilities in the hotel, the everlasting friendliness of the Chinese organizers, and a very interesting bus excursion to the touristic highlights of Nanjing, there were lots of possibilities to establish new scientific contacts or intensify existing ones. Juergen Wolff von Gudenberg From owner-reliable_computing Wed May 13 13:47:59 1998 Received: by interval.usl.edu id AA17879 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Wed, 13 May 1998 11:54:44 -0500 Received: from mailserver.di.unipi.it (memphis.di.unipi.it) by interval.usl.edu with SMTP id AA17873 (5.65c/IDA-1.4.4 for ); Wed, 13 May 1998 11:54:33 -0500 Organization: Dipartimento di Informatica di Pisa - Italy Received: from mox.di.unipi.it (mox.di.unipi.it [131.114.4.238]) by mailserver.di.unipi.it (8.8.8/8.8.8) with SMTP id LAA26625; Wed, 13 May 1998 11:33:30 +0200 (MET DST) Message-Id: <3.0.5.32.19980513114759.00798e20 [at] mailserver [dot] di.unipi.it> X-Sender: bista [at] mailserver [dot] di.unipi.it (Unverified) X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32) Date: Wed, 13 May 1998 11:47:59 +0200 To: (Recipient list suppressed) From: Stefano Bistarelli Subject: CFP: CP98 workshop on constraints in biocomputing Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-reliable_computing Precedence: bulk --------------------------------------------------------- Apologies if you receive this more than once! --------------------------------------------------------- --------------------------------------------------------------------- CALL FOR PAPERS --------------------------------------------------------------------- CP98 Workshop on Constraints in Bioinformatics/Biocomputing (http://www.cs.city.ac.uk/~drg/cp98-workshop/cp98-workshop.html) -------------------------------------------------------------------- Pisa, Italy 30 October 1998 -------------------------------------------------------------------- The workshop will be held in conjunction with the Fourth International Conference on Principles and Practice of Constraint Programming (CP98), October 26-30, 1998 at Pisa, Italy. Scope of the workshop Bioinformatics is the development and application of methods in mathematics and informatics for approaching problems in molecular biology, whereas Biocomputing uses naturally occurring architectures and behaviours as models for computational methods, for example neural networks, genetic algorithms, genetic programming and DNA computing. This is the second workshop on this topic, in an very exciting and rapidly expanding area; selected papers from the first workshop will appear in a special issue of the Constraints Journal. We believe that constraint programming technologies can play a very significant role in these fast developing areas. Contributions are solicited from researchers working in any of these fields. Topics include (but are not restricted to) the application of constraint technology to * sequencing and sequence analysis * languages for the description of biomolecular structures (primary, secondary and tertiary) * design and implementation of biomolecular databases * algorithms for locating structures in biomolecular databases * protein topology, including prediction and folding pathways * determination of protein domains * molecular docking problems * description and determination of metabolic pathways * determination of evolutionary relationships * discovery and data mining of biostructures * genetic and physical mapping * DNA rearrangement * sequence alignment * phylogeny * neural networks * genetic algorithms * genetic programs * DNA computing Papers that combine theory and practice are especially welcome. Authors are strongly encouraged to ensure high quality of both the biological as well as the computer science aspects of their submissions. Paper submissions Authors are invited to submit original papers written in English and approximately 10 A4 pages in length to David Gilbert (drg [at] cs [dot] city.ac.uk) at the contact address below. We encourage authors to submit by electronic mail in self-contained Postscript format. Alternatively five paper copies may be submitted. Publication An informal proceedings of the workshop will be available on-line prior to the workshop. It is expected that selected papers will either be published as a book or as an international journal issue. Organisation David Gilbert, City University, UK, drg [at] cs [dot] city.ac.uk Rolf Backofen, Ludwig-Maximilians-Universitaet Muenchen, Germany, backofen [at] informatik [dot] uni-muenchen.de Geoff Barton, European BioInformatics Institute, Cambridge UK, geoff [at] ebi [dot] ac.uk Ingvar Eidhammer, University of Bergen, Norway, ingvar [at] ii [dot] uib.no Christine Gaspin, National Institute of Agronomical Research, France, gaspin [at] toulouse [dot] inra.fr Roland Yap, National University of Singapore, ryap [at] iscs [dot] nus.edu.sg Important dates 15 August 1998 Paper submissions 15 September 1998 Acceptance decisions 10 October 1998 Final copy due 30 October 1998 Workshop Further information The workshop web-site is http://www.cs.city.ac.uk/~drg/cp98-workshop/cp98-workshop.html Information on CP98 is available at the CP98 web site: http://www.di.unipi.it/cp98/ From owner-reliable_computing Wed May 13 15:22:13 1998 Received: by interval.usl.edu id AA18059 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Wed, 13 May 1998 12:22:44 -0500 Received: from mailserver.di.unipi.it (memphis.di.unipi.it) by interval.usl.edu with SMTP id AA18053 (5.65c/IDA-1.4.4 for ); Wed, 13 May 1998 12:22:40 -0500 Organization: Dipartimento di Informatica di Pisa - Italy Received: from mox.di.unipi.it (mox.di.unipi.it [131.114.4.238]) by mailserver.di.unipi.it (8.8.8/8.8.8) with SMTP id NAA03949; Wed, 13 May 1998 13:07:43 +0200 (MET DST) Message-Id: <3.0.5.32.19980513132213.0079a1b0 [at] mailserver [dot] di.unipi.it> X-Sender: bista [at] mailserver [dot] di.unipi.it (Unverified) X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32) Date: Wed, 13 May 1998 13:22:13 +0200 To: (Recipient list suppressed) From: Stefano Bistarelli Subject: CFP: CP98 workshop on large scale combinatorial optimization Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-reliable_computing Precedence: bulk --------------------------------------------------------------------- CALL FOR PAPERS --------------------------------------------------------------------- CP98 Workshop on Large Scale Combinatorial Optimisation and Constraints (http://www.icparc.ic.ac.uk/~mgw/chic2_workshop.html) -------------------------------------------------------------------- Pisa, Italy 30 October 1998 -------------------------------------------------------------------- (in conjunction with the fourth International Conference on Principles and Practice of Constraint Programming (CP98)) -------------------------------------------------------------------- This workshop will explore hybrid algorithms for complex optimisation problems. These will be based on the integration of different approaches, viz. constraint programming, mathematical programming and stochastic repair techniques. These approaches have sometimes been perceived as competitors, but more recently they have come to be seen as complementary. The need for such algorithms in solving optimisation problems arises from the fact that different techniques are suited to solving different aspects of the problem. Among the key techniques are constraint propagation, Lagrangean relaxation, linear programming, randomised search and local optimisation. Constraint propagation is ideal for customising an algorithm with domain-dependent constraints. Lagrangean relaxation is the technique of choice for obtaining lower bounds in a branch and bound approach. Linear programming is the only technique that can solve to optimiality large linear problems. Randomised search is necessary for problems that are too large for branch and bound. Local optimisation is the preferred technique for problems that have a specific neighbourhood structure, such as routing problems. Many optimisation problems are hybrid, embracing several different requirements. For example real-life dispatching problems involve both matching, routing and scheduling. For such problems there is a clear need to mix techniques. This mixing can take different forms. On one hand generic methods, such as tabu search or constraint propagation can be significantly enhanced by importing techniques developed for branch and bound (such as edge-finding) or for local optimisation (such as neighbourhood structure). On the other hand different techniques can be applied at different stages of the search. For instance initial solutions can be found using constructive search with constraint propagation, and the solution can then be improved through local optimisation. The workshop invites submissions related to LSCO and Constraints. Topics of interest include: -- hybrid algorithms -- LSCO applications solved using hybrid algorithms -- Methods for integrating different techniques -- Methodologies for devising application-specific hybrid algorithms -- Platforms supporting experimentation with hybrid algorithms -- Surveys of existing hybrid techniques and related literature PAPER SUBMISSIONS: Submission deadline is 15 August 1998. Authors are invited to submit original papers written in English and approximately 10 A4 pages to either Mark Wallace or Yves Caseau at the contact address below. We encourage authors to submit by electronic mail in Word or self-contained Postscript format. Alternatively 3 paper copies may be submitted by post. Decisions on acceptance will be sent to authors by by 15 September 1998. ORGANISATION: -- Mark Wallace IC-Parc, William Penney Laboratory Imperial College, London SW7 2BZ, UK email: mgw [at] icparc [dot] ic.ac.uk -- Yves Caseau Bouygues, Challenger, 1 Av Eugene Freyssinet, 78061 St-Quentin-Yvelines Cedex, FRANCE email: ycs [at] challenger [dot] bouygues.fr -- Eric Jacquet-Lagreze, EuroDecision -- Helmut Simonis, Cosytec -- Gilles Pesant Centre for Research on Transportation, Univ. Montreal IMPORTANT DATES: -- 15 August 1998: Paper submissions -- 15 September 1998: Acceptance decisions -- 10 October 1998: Final copy due -- 30 October 1998: Workshop FURTHER INFORMATION: Additional information about CP98 will be available at the CP98 web site: http://www.di.unipi.it/cp98/ From owner-reliable_computing Fri May 15 17:50:36 1998 Received: by interval.usl.edu id AA22511 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 15 May 1998 12:54:57 -0500 Received: from mailserver.di.unipi.it (memphis.di.unipi.it) by interval.usl.edu with SMTP id AA22505 (5.65c/IDA-1.4.4 for ); Fri, 15 May 1998 12:54:48 -0500 Organization: Dipartimento di Informatica di Pisa - Italy Received: from mox.di.unipi.it (mox.di.unipi.it [131.114.4.238]) by mailserver.di.unipi.it (8.8.8/8.8.8) with SMTP id PAA23053; Fri, 15 May 1998 15:35:55 +0200 (MET DST) Message-Id: <3.0.5.32.19980515155036.0079b690 [at] mailserver [dot] di.unipi.it> X-Sender: bista [at] mailserver [dot] di.unipi.it (Unverified) X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32) Date: Fri, 15 May 1998 15:50:36 +0200 To: (Recipient list suppressed) From: Stefano Bistarelli Subject: CFP: CP98 workshop on constraint problem reformulation Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-reliable_computing Precedence: bulk --------------------------------------------------------- Apologies if you receive this more than once! --------------------------------------------------------- --------------------------------------------------------------------- CALL FOR PAPERS --------------------------------------------------------------------- CP98 Workshop on Constraint Problem Reformulation (http://ic-www.arc.nasa.gov/ic/people/frank/workshop.html) --------------------------------------------------------------------- Pisa, Italy 30 October 1998 --------------------------------------------------------------------- (in conjunction with the fourth International Conference on Principles and Practice of Constraint Programming (CP98)) --------------------------------------------------------------------- This workshop will focus on reformulating Constraints Problems to take advantage of efficient techniques in particular constraints problem domains. In particular, the workshop will focus on reformulating NP-Complete problems and related optimization problems to translate them to domains which have good problem solver performance A fundamental issue is planning and search is the choice of an appropriate problem representation. While the importance of problem representation has been widely recognized within AI, starting from the work of Saul Amarel on represenations of the Missionaries and Cannibals, there have not been a great many success stories. Much research focuses on exploiting the domain-specific details of a particular problem domain in order to come up with the best algorithm. However, there is considerable value to exploring alternate representations for which good algorithms already exist. For eaxmple, SATPLAN exploits the excellent performance of algorithms (both deterministic and non-deterministic) to solve SAT problem instances. SATPLAN's success is hard-won, however, in that automatic procedures for translating planning problems to SAT representation are not as effective as hand-designed representations. Other efforts at reformulation, such as encoding Hamiltonian Cycle problems as SAT problems and using local search to solve them, have not been successful. WORKSHOP FOCUS: Issues which workshop submissions will focus on include: What are the issues in reformulation? Speed of translation procedure. Exposing/hiding of information by the translation procedure. Translation by hand vs. automated translation. Translation of problem classes vs. translation of problem instances. How should reformulation be used? Reformulation to solve problems directly. Reformulation to motivate improvements in the original space. Explaining success/failure of reformulation. A more detailed explanation of the workhshop themes can be found in the extended workshop announcement, which is available on the workshop web page. Paper Submission and Important Dates Prospective authors are asked to submit papers of 6 pages or less in length. The papers should be original, written in English, and formatted on either 8.5 by 11 inches or A4 paper. Papers may be sent electronically, with appropriate instructions, or by mail. Submissions should be submitted to both Jeremy Frank and Mihaela Sabin; contact information is provided at the end of the call. Workshop attendees are asked to send a 1 page statement of interest; all of these statements will be published with the workshop proceedings. August 28, 1998: Submission of workshop papers. September 11, 1998: Announcement of workshop speakers and posting of workshop schedule. September 25, 1998: Submission of statement of interest by workshop attendees. September 25, 1998: Final copy of the accepted papers due. October 30, 1998: Workshop occurs in conjunction with CP 98 in Pisa, Italy. Publication With the authors permission, we will publish all of the accepted papers on the workshop web site. We will also publish the papers and statements of interest, along with the introductory components of the workshop call for papers, in a booklet which will be made available at the workshop. Workshop Format The morning session will be reserved for presentations: each presentation will be limited to 20 minutes. A 3.5 hour morning session leaves time for roughly 10 presentations of 20 minutes each. The afternoon session would then be reserved for free-form discussion on the topics presented in the morning, with about a half-hour wrap up. The accompanying workshop proceedings will include a 6 page paper for each speaker, plus 1 page statements of interest from any other participants. Contact Information Jeremy Frank Caelum Research Corp. Mail Stop 269-1 NASA Ames Research Center Moffett Field, CA 94040 frank [at] ptolemy [dot] arc.nasa.gov Mihaela Sabin Computer Science Department University of New Hampshire Durham, NH 03824 mcs [at] cs [dot] unh.edu Constraint Programming 1998 page: http://www.di.unipi.it/cp98/ Constraint Problem Reformulation Workshop page: http://ic-www.arc.nasa.gov/ic/people/frank/workshop.html From owner-reliable_computing Sat May 16 11:52:52 1998 Received: by interval.usl.edu id AA23575 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sat, 16 May 1998 18:52:59 -0500 Received: from cs.utep.edu by interval.usl.edu with SMTP id AA23569 (5.65c/IDA-1.4.4 for ); Sat, 16 May 1998 18:52:56 -0500 Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1) id AA15826; Sat, 16 May 98 17:52:52 MDT Date: Sat, 16 May 98 17:52:52 MDT From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich) Message-Id: <9805162352.AA15826 [at] cs [dot] utep.edu> To: reliable_computing [at] interval [dot] usl.edu, interval [at] cs [dot] utep.edu Subject: contents of RC 3-98 Cc: leonid [at] cs [dot] utep.edu, hunguyen [at] nmsu [dot] edu, doser [at] geo [dot] utep.edu, olga [at] ece [dot] utep.edu Sender: owner-reliable_computing Precedence: bulk ----- Begin Included Message ----- From slava!slava.nit.spb.su!nest [at] into [dot] nit.spb.su Mon May 11 13:54:57 1998 To: vladik [at] cs [dot] utep.edu Organization: Slava Nesterov Date: Mon, 11 May 1998 23:56:12 +0400 (MSD) Reply-To: nest [at] into [dot] nit.spb.su From: "Slava Nesterov" X-Mailer: dMail [Demos Mail for DOS v1.23] Subject: contents of 3-98 Lines: 63 Content-Length: 1314 Dear Vladik, Find attached the table of contents of the issue 3-98 Yours, Slava 3-98 Mathematical Research On the Applicability of the Interval Gaussian Algorithm G"unter Mayer, Jiri Rohn 205-222 On a Second Derivative Test due to Qi Michael A. Wolfe 223-234 Universal Approximation Theorem for Interval Neural Networks Mark R. Baker, Rajendra B. Patil 235-239 Applications Estimating Uncertainties for Geophysical Tomography Diane I. Doser, Kevin D. Crain, Mark R. Baker, Vladik Kreinovich, Matthew C. Gerstenberger 241-268 The Use of Interval Analysis in Hydrologic Systems Tiraz R. Birdie, Karan S. Surana 269-281 An Application of Fuzzy Mathematical Morphology to Interval-Valued Knowledge Representation: A Remark Antony T. Popov, Hung T. Nguyen, Leonid K. Reznik 283-290 Interval + Image = Wavelet: For Image Processing under Interval Uncertainty, Wavelets Are Optimal Alejandro E. Brito, Olga Kosheleva 291-301 Short Communication Exclusive OR Operation That Leads to the Narrowest Intervals Alfredo Gabaldon, Hung T. Nguyen 303-306 Review Review of the book O.Aberth: Precise Numerical Methods Using C++, Academic Press, 1998. 307-308 Information International Conference Interval'98 309  ----- End Included Message ----- From owner-reliable_computing Mon May 18 02:17:24 1998 Received: by interval.usl.edu id AA26015 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 18 May 1998 11:17:53 -0500 Received: from mercury.Sun.COM by interval.usl.edu with SMTP id AA26009 (5.65c/IDA-1.4.4 for ); Mon, 18 May 1998 11:17:51 -0500 Received: from Eng.Sun.COM (engmail3 [129.144.170.5]) by mercury.Sun.COM (SMI-8.6/mail.byaddr) with SMTP id JAA12965 for ; Mon, 18 May 1998 09:17:41 -0700 Received: from thestork.eng.sun.com (thestork.Eng.Sun.COM [129.146.88.47]) by Eng.Sun.COM (SMI-8.6/SMI-5.3) with ESMTP id JAA12436 for ; Mon, 18 May 1998 09:17:41 -0700 Received: from math (math.Eng.Sun.COM) by thestork.eng.sun.com (Sun Internet Mail Server sims.3.2.1998.05.04.15.32) with SMTP id <0ET5005AHULFKQ [at] thestork [dot] eng.sun.com> for reliable_computing [at] interval [dot] usl.edu; Mon, 18 May 1998 09:17:40 -0700 (PDT) Date: Mon, 18 May 1998 09:17:24 -0700 (PDT) From: Dmitri Shiriaev Subject: arbitrary precision interval arithmetic in C++ ? To: reliable_computing [at] interval [dot] usl.edu Cc: interval_all [at] gww [dot] eng.sun.com Reply-To: Dmitri Shiriaev Message-Id: <0ET5005AIULGKQ [at] thestork [dot] eng.sun.com> Mime-Version: 1.0 X-Mailer: dtmail 1.2.1 CDE Version 1.2.1 SunOS 5.6 sun4u sparc Content-Type: TEXT/plain; charset=us-ascii Content-Md5: /8u9ARTrr17f6guXDi3MFw== Sender: owner-reliable_computing Precedence: bulk Friends, Could somebody send me a pointer to J. Ely's VPI interval arithmetic library and the latest version of O.Aberth's interval arithmetic in C++ Does anybody know about any other libraries (except C-XSC) implementing arbitrary precision interval arithmetic in C++ ? Thank you Regards -- Dima -- From owner-reliable_computing Tue May 19 21:18:36 1998 Received: by interval.usl.edu id AA29963 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Wed, 20 May 1998 13:45:08 -0500 Received: from riscfo (riscfo.spfo.unibo.it) by interval.usl.edu with SMTP id AA29957 (5.65c/IDA-1.4.4 for ); Wed, 20 May 1998 13:45:03 -0500 Received: from [137.204.203.22] by riscfo (AIX 3.1/UCB 5.61/4.03) id AA05953; Wed, 20 May 98 20:18:36 -2300 Date: Wed, 20 May 98 20:18:36 -2300 Message-Id: <9805211918.AA05953@riscfo> X-Sender: bista [at] mailserver [dot] di.unipi.it (Unverified) X-Mailer: Windows Eudora Light Version 1.5.2 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit To: (Recipient list suppressed) From: bista [at] di [dot] unipi.it Subject: CFP: CP98 workshop on set constraints and constraint-based program analysis Sender: owner-reliable_computing Precedence: bulk --------------------------------------------------------------------- CALL FOR PAPERS --------------------------------------------------------------------- CP98 Workshop on Set Constraints and Constraint-based Program Analysis (http://www.mpi-sb.mpg.de/~podelski/conferences/sc98.html) --------------------------------------------------------------------- Pisa, Italy 30 October 1998 --------------------------------------------------------------------- (in conjunction with the Fourth International Conference on Principles and Practice of Constraint Programming, http://www.di.unipi.it/cp98/) --------------------------------------------------------------------- Scope: The first uses of set constraints date back at least to John Reynold's early work on program analysis in 1969. In the last decade there has been a significant increase in the interest in set constraints, with major advances both in the foundations of set constraints as well as in applications. Meanwhile, constraints have become a core technology in areas such as types and program analysis. Constraint-based approaches have led to many algorithmic and conceptual advances in type inference (particularly subtypes), data-flow analysis, control-flow analysis, binding-time analysis, and sorted-unification. Many of these works directly use set constraints; other used equational and constraint theories of which set constraints are a generalization. Organizing Committee: Alexander Aiken (UC Berkeley, U.S.A.) Harald Ganzinger (Max Planck Institute, Germany) Nevin Heintze (Bell Laboratories, U.S.A.) Fritz Henglein (DIKU, University of Copenhagen) Joxan Jaffar (National University of Singapore) Bruno Legeard (Univ. of Franche-Comti, France) David McAllester (AT&T Laboratories, U.S.A.) Leszek Pacholski (University of Wroclaw, Poland) Jens Palsberg (Purdue University) Andreas Podelski (Max Planck Institute, Germany) Jean-Francois Puget (ILOG, France) Jakob Rehof (Microsoft Research, U.S.A.) Sophie Tison (University of Lille, France) Submission Details: Authors are invited to submit short papers (2-8 pages) for presentation at the workshop, by email to podelski@mpi-sb.mpg.de. Papers may describe preliminary or partial results as well as finished research. Position papers are also welcome. Topics of interest include, but are not limited to: - decision procedures and algorithms, - applications, - implementation, - connections with other areas such as model checking. The aim of this workshop is to bring together researchers working on all aspects of set constraints, and provide a forum for discussing novel applications, implementation, new results and open problems. We also hope that the workshop will give a sense of the diversity of set constraints applications, and in so doing generate new problems, approaches, and opportunities. Submissions deadline: July 15, 1998 Acceptance decisions: August 20 Camera-ready deadline: September 20 Workshop: October 30 From owner-reliable_computing Mon May 25 01:27:29 1998 Received: by interval.usl.edu id AA03646 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sun, 24 May 1998 14:27:55 -0500 Received: from TopGun.softserve.lviv.ua by interval.usl.edu with SMTP id AA03640 (5.65c/IDA-1.4.4 for ); Sun, 24 May 1998 14:27:42 -0500 Received: from SoftServe.Lviv.UA (dx200.softserve.lviv.ua [194.44.33.237]) by topgun.softserve.lviv.ua (8.8.7/8.7.3) with ESMTP id WAA30949 for ; Sun, 24 May 1998 22:27:16 +0300 Message-Id: <3568749E.3BDDF1F1 [at] SoftServe [dot] Lviv.UA> Date: Sun, 24 May 1998 22:27:29 +0300 From: Sergiy Kornienko X-Mailer: Mozilla 4.04 [en] (Win95; I) Mime-Version: 1.0 To: reliable_computing Subject: About algorithm for solving nonlinear equations. Content-Type: text/plain; charset=koi8-r Content-Transfer-Encoding: 7bit Sender: owner-reliable_computing Precedence: bulk Dear Sir, I am postgraduate student interested in interval analysis. Now, I am looking for efficient algorithms for solving a system of nonlinear equations with interval coefficients. Please answer me, if you know any published works or WWW-sites about this problem. Thank you. Sergiy Kornienko Lviv, Tarnavskogo str 104a/3 Ukraine. From owner-reliable_computing Sun May 24 13:07:42 1998 Received: by interval.usl.edu id AA03988 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sun, 24 May 1998 16:12:19 -0500 Received: from yonge.cs.toronto.edu by interval.usl.edu with SMTP id AA03982 (5.65c/IDA-1.4.4 for ); Sun, 24 May 1998 16:11:51 -0500 Received: from dvp.cs.toronto.edu ([128.100.1.15]) by yonge.cs.toronto.edu with SMTP id <86521-29920>; Sun, 24 May 1998 17:08:01 -0400 Received: by dvp.cs.toronto.edu id <15470-621>; Sun, 24 May 1998 17:07:49 -0400 From: Jeff Tupper To: reliable_computing [at] interval [dot] usl.edu Subject: GrafEq 2.04 / IA graphing software Cc: peda [at] peda [dot] com Content-Length: 2394 Message-Id: <98May24.170749edt.15470-621 [at] dvp [dot] cs.toronto.edu> Date: Sun, 24 May 1998 17:07:42 -0400 Sender: owner-reliable_computing Precedence: bulk Hello all, As a number of researchers on this list have been interested in GrafEq, I am announcing the general availability of GrafEq 2.04 here. A major difference, for the readers of this list, is that you (anyone) can now download a fully-functional evaluation copy of GrafEq at http://www.peda.com/grafeq/down.html GrafEq is a program that graphs implicit relations - it presents a two dimensional view (an orthographic projection if the relation is in more than two dimensions) of entered relations. I think that it demonstrates the general superiority of interval techniques over traditional floating point techniques as it is not fooled as other graphing programs are, by relations such as y=sin1/x or y=Arctan9^9^9(x-1) and naturally allows a variety of relations, such as 1/(x^2+y^2-25)=0 or 1/(x^2+y^2-25)<0 or x+y=|x+y| It is convincing since it not only automatically handles (traditionally) difficult cases, but it is in many cases faster than traditional graphing software (such as maple, mathematica, etc...) since they try to improve reliability by employing complex methods. (Note that GrafEq employs simple methods, and many difficult graphs could be produced much more efficiently by more sophisticated interval methods.) With GrafEq, there is a precise definition of when a pixel should be "on": a pixel is "on" iff there is a solution to the relation within the region of space represented by that pixel. (With other graphing software, there is no easily understood definition of when a pixel is "on".) With 2d, that corresponds to a rectangular region of the plane (with (n+2) dimensions, it is the inverse image of the planar rectangle under the orthographic projection). GrafEq will attempt to prove that there is (or is not) a solution to the relation within each pixel using interval arithmetic techniques described in my M.Sc. thesis (http://www.dgp.toronto.edu/people/mooncake/msc.html). Some of the techniques described in the thesis are not used in the generally-available versions of GrafEq, although they would improve its performance. If, after you have used it, you would like to have a license for further use and/or demonstration, I have arranged for no-cost individual licenses for interval arithmetic researchers - contact me for further information. As always, I appreciate any and all comments and questions. Jeff Tupper From owner-reliable_computing Mon May 25 02:46:40 1998 Received: by interval.usl.edu id AA04522 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Mon, 25 May 1998 07:47:04 -0500 Received: from boris.mscs.mu.edu by interval.usl.edu with SMTP id AA04516 (5.65c/IDA-1.4.4 for ); Mon, 25 May 1998 07:47:00 -0500 Received: by boris.mscs.mu.edu (Smail3.1.28.1 #9) id m0ydweG-001HcaC; Mon, 25 May 98 07:46 CDT Message-Id: From: georgec [at] marque [dot] mscs.mu.edu (Dr. George F. Corliss MU MSCS) Subject: About algorithm for solving nonlinear equations. (fwd) To: skornien [at] softserve [dot] lviv.ua Date: Mon, 25 May 1998 07:46:40 -0500 (CDT) Cc: reliable_computing [at] interval [dot] usl.edu X-Mailer: ELM [version 2.4 PL25] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1722 Sender: owner-reliable_computing Precedence: bulk Sergiy, > I am postgraduate student interested in interval analysis. > Now, I am looking for efficient algorithms for solving a system of > nonlinear equations with interval coefficients. > Please answer me, if you know any published works or WWW-sites about > this problem. Good books include: @BOOK { Hansen1992a, AUTHOR = "Elden R. Hansen", TITLE = "Global Optimization Using Interval Analysis", PUBLISHER = "Marcel Dekker", SERIES = "", NUMBER = "", ADDRESS = "New York", YEAR = "1992", REFERRED = "[Jerrell1996a], [Rall1996a].", ISBN = "0824786963", COMMENTS = "", KEYWORDS = "", ABSTRACT = "", } @BOOK { Kearfott1996b, AUTHOR = "R. Baker Kearfott", TITLE = "Rigorous Global Search: Continuous Problems", PUBLISHER = "Kluwer Academic Publishers", SERIES = "", NUMBER = "", ADDRESS = "Dordrecht, Netherlands", YEAR = "1996", REFERRED = "[Jerrell1996a], [Kearfott1996a].", ISBN = "", COMMENTS = "", KEYWORDS = "", ABSTRACT = "", } @BOOK { Neumaier1990a, AUTHOR = "Arnold Neumaier", TITLE = "Interval Methods for Systems of Equations", PUBLISHER = "Cambridge University Press", SERIES = "", NUMBER = "", ADDRESS = "Cambridge", YEAR = "1990", REFERRED = "[Kearfott1996a].", ISBN = "0--521--33196--X", COMMENTS = "", KEYWORDS = "", ABSTRACT = "", } Neumaier's Web site: http://solon.cma.univie.ac.at/~neum/glopt.html Corliss/Kearfott GlobSol Web site: http://www.mscs.mu.edu/~globsol George F. Corliss Dept. Math, Stat, Comp Sci Marquette University P.O. Box 1881 Milwaukee, WI 53201-1881 USA georgec [at] mscs [dot] mu.edu; CorlissG [at] Marquette [dot] edu http://www.mscs.mu.edu/~georgec/ Office: 414-288-6599; Dept: 288-7375; Fax: 288-5472 From owner-reliable_computing Tue May 26 13:03:42 1998 Received: by interval.usl.edu id AA09491 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 26 May 1998 06:12:22 -0500 Received: from ohio.mech.gla.ac.uk ([130.209.12.42]) by interval.usl.edu with SMTP id AA09483 (5.65c/IDA-1.4.4 for ); Tue, 26 May 1998 06:04:06 -0500 Received: (from qyang@localhost) by ohio.mech.gla.ac.uk (8.8.7/8.8.7) id MAA12250 for reliable_computing [at] interval [dot] usl.edu; Tue, 26 May 1998 12:03:42 +0100 (BST) Date: Tue, 26 May 1998 12:03:42 +0100 (BST) From: QI Yang Message-Id: <199805261103.MAA12250 [at] ohio [dot] mech.gla.ac.uk> To: reliable_computing [at] interval [dot] usl.edu Subject: Interval ODE X-Sun-Charset: US-ASCII Sender: owner-reliable_computing Precedence: bulk Hello all, I am a Ph.D student and I am very interested in the interval methed for ODE. Consider the initial valve problem: dx/dt=f(t, c, x) x(t0)=[a, b]; where parameter vector c or/and the initial conditons are all represented by the intervals. I would appreciate it if someone would tell me where can I get software to solvethis problem or to recommand some good papers on this topic. best regards Qiugui Yang Mech. Eng. University of Glasgow United Kingdom From owner-reliable_computing Tue May 26 22:00:22 1998 Received: by interval.usl.edu id AA09653 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 26 May 1998 10:29:16 -0500 Received: from nsc.ru by interval.usl.edu with SMTP id AA09629 (5.65c/IDA-1.4.4 for ); Tue, 26 May 1998 10:23:38 -0500 Received: from hooker.iis.nsk.su (hooker.iis.nsk.su [194.226.177.235]) by nsc.ru (8.8.8/1.37) id WAA19206; Tue, 26 May 1998 22:22:01 +0700 (NSD) Message-Id: <199805261522.WAA19206 [at] nsc [dot] ru> Comments: Authenticated sender is From: "Alexander Semenov" Organization: Russian Research Institute of AI To: Sergiy Kornienko Date: Tue, 26 May 1998 21:54:22 +6 Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT Subject: Re: About algorithm for solving nonlinear equations. Reply-To: semenov [at] iis [dot] nsk.su Cc: reliable_computing Priority: normal In-Reply-To: <3568749E.3BDDF1F1 [at] SoftServe [dot] Lviv.UA> X-Mailer: Pegasus Mail for Win32 (v2.53/R1) Sender: owner-reliable_computing Precedence: bulk Sergiy, Look at our web site http://www.rriai.org.ru/UniCalc >From this site you can download a demo version of a solver of nonlinear systems (including interval ones). Best regards, Alexander Semenov --------------------------------------------------------------------------- Alexander Semenov Novosibirsk Division of the Russian Research Institute of Artificial Intelligence tel. (7 383 2) 34 29 91 pr. ak. Lavrent'eva, 6 fax (7 383 2) 32 83 59 Novosibirsk e-mail semenov [at] iis [dot] nsk.su Russia, 630090 URL http://www.rriai.org.ru/~semenov/ ------------------------------------------------------------------- From owner-reliable_computing Tue May 26 12:06:33 1998 Received: by interval.usl.edu id AA14196 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 26 May 1998 17:07:02 -0500 Received: from boris.mscs.mu.edu by interval.usl.edu with SMTP id AA14190 (5.65c/IDA-1.4.4 for ); Tue, 26 May 1998 17:06:55 -0500 Received: by boris.mscs.mu.edu (Smail3.1.28.1 #9) id m0yeRrd-001HcaC; Tue, 26 May 98 17:06 CDT Message-Id: From: georgec [at] marque [dot] mscs.mu.edu (Dr. George F. Corliss MU MSCS) Subject: Re: Interval ODE To: qyang [at] mech [dot] gla.ac.uk (QI Yang) Date: Tue, 26 May 1998 17:06:33 -0500 (CDT) Cc: reliable_computing [at] interval [dot] usl.edu, georgec [at] marque [dot] mscs.mu.edu (George Corliss), Rudolf.Lohner [at] math [dot] uni-karlsruhe.de, km [at] imm [dot] dtu.dk, berz [at] pilot [dot] msu.edu, ned [at] cs [dot] toronto.edu, pryce [at] rmcs [dot] cranfield.ac.uk, robert.rihm [at] math [dot] uni-karlsruhe.de In-Reply-To: <199805261103.MAA12250 [at] ohio [dot] mech.gla.ac.uk> from "QI Yang" at May 26, 98 12:03:42 pm X-Mailer: ELM [version 2.4 PL25] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1154 Sender: owner-reliable_computing Precedence: bulk Qiugui, I know of three software packages: 1. Rudolph Lohner, AWA, Rudolf.Lohner [at] math [dot] uni-karlsruhe.de http://www.uni-karlsruhe.de/~Rudolf.Lohner/english/ 2. Ole Staunung, c/o Kaj Madsen, km [at] imm [dot] dtu.dk See papers linked at http://www.imm.dtu.dk/documents/users/km/int.html 3. Martin Berz, COSY, berz [at] pilot [dot] msu.edu http://www.beamtheory.nscl.msu.edu/cosy/ Other researchers of note in the field include Ned Nedialkov, ned [at] cs [dot] toronto.edu John Pryce, pryce [at] rmcs [dot] cranfield.ac.uk Robert Rihm, robert.rihm [at] math [dot] uni-karlsruhe.de > I would appreciate it if someone would tell me where can I get software to solvethis problem or to recommand some good papers on this topic. See also Where is Validated ODE Solving Going? http://www.mscs.mu.edu/~georgec/Pubs/Corliss1996d/ Survey of Validated ODEs ftp from boris.mscs.mu.edu cd pub/corliss/ValidODE Both Nedialkov and Rihm have also written excellent surveys. George F. Corliss Dept. Math, Stat, Comp Sci Marquette University P.O. Box 1881 Milwaukee, WI 53201-1881 USA georgec [at] mscs [dot] mu.edu; CorlissG [at] Marquette [dot] edu http://www.mscs.mu.edu/~georgec/ Office: 414-288-6599; Dept: 288-7375; Fax: 288-5472 From owner-reliable_computing Wed May 27 12:12:36 1998 Received: by interval.usl.edu id AA14734 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Wed, 27 May 1998 05:13:38 -0500 Received: from gps1.leeds.ac.uk (gps1-fddi.leeds.ac.uk) by interval.usl.edu with SMTP id AA14728 (5.65c/IDA-1.4.4 for ); Wed, 27 May 1998 05:13:31 -0500 Received: from mi.leeds.ac.uk (misun1.leeds.ac.uk [129.11.12.4]) by gps1.leeds.ac.uk (8.8.8/8.8.8) with SMTP id LAA15503 for ; Wed, 27 May 1998 11:12:38 +0100 (BST) Message-Id: <356BE714.52BF [at] mi [dot] leeds.ac.uk> Date: Wed, 27 May 1998 11:12:36 +0100 From: Zsuzsanna Szabo Organization: ICAMS, School of Chemistry, Univ. of Leeds X-Mailer: Mozilla 3.04Gold (X11; I; IRIX 6.2 IP22) Mime-Version: 1.0 To: reliable_computing [at] interval [dot] usl.edu Subject: dependency problem Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-reliable_computing Precedence: bulk Hello, I would appreciate if someone could tell me about methods for treating the dependency problem in interval arithmetics (methods like affine arithmetics or preconditioning). Thank You, Zsuzsanna Szabo University of Leeds UK From owner-reliable_computing Wed May 27 02:21:14 1998 Received: by interval.usl.edu id AA15087 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Wed, 27 May 1998 07:21:37 -0500 Received: from boris.mscs.mu.edu by interval.usl.edu with SMTP id AA15081 (5.65c/IDA-1.4.4 for ); Wed, 27 May 1998 07:21:33 -0500 Received: by boris.mscs.mu.edu (Smail3.1.28.1 #9) id m0yefCl-001HcaC; Wed, 27 May 98 07:21 CDT Message-Id: From: georgec [at] marque [dot] mscs.mu.edu (Dr. George F. Corliss MU MSCS) Subject: Re: dependency problem To: zsu [at] mi [dot] leeds.ac.uk (Zsuzsanna Szabo) Date: Wed, 27 May 1998 07:21:14 -0500 (CDT) Cc: reliable_computing [at] interval [dot] usl.edu In-Reply-To: <356BE714.52BF [at] mi [dot] leeds.ac.uk> from "Zsuzsanna Szabo" at May 27, 98 11:12:36 am X-Mailer: ELM [version 2.4 PL25] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1072 Sender: owner-reliable_computing Precedence: bulk Zsuzsanna, > I would appreciate if someone could tell me about methods for treating > the dependency problem in interval arithmetics (methods like affine > arithmetics or preconditioning). First, read the book by Neumaier. Various approaches include: 1. Rearrangement. 2. Re-formulation of expressions as linear or nonlinear systems People in Karlsruhe did work in this area 15 years ago 3. Centered, mean value, or higher order Taylor forms 4. Martin Berz's approach of floating-point truncated Taylor polynomial + one constant interval remainder 5. Markov uses an arithmetic that keeps track of monotonicities in intermediate results 6. Attack the range bounding problem with full interval global optimization machinery, e.g. GlobSol 7. Stoic acceptance of the inevitable :-) George F. Corliss Dept. Math, Stat, Comp Sci Marquette University P.O. Box 1881 Milwaukee, WI 53201-1881 USA georgec [at] mscs [dot] mu.edu; CorlissG [at] Marquette [dot] edu http://www.mscs.mu.edu/~georgec/ Office: 414-288-6599; Dept: 288-7375; Fax: 288-5472 From owner-reliable_computing Wed May 27 11:39:43 1998 Received: by interval.usl.edu id AA15774 (5.65c/IDA-1.4.4 for reliable_computing-outgoing); Wed, 27 May 1998 12:41:19 -0500 Received: from grande.dcc.unicamp.br by interval.usl.edu with SMTP id AA15768 (5.65c/IDA-1.4.4 for ); Wed, 27 May 1998 12:40:45 -0500 Received: from amazonas.dcc.unicamp.br (amazonas.dcc.unicamp.br [143.106.7.11]) by grande.dcc.unicamp.br (8.8.5/8.8.5) with ESMTP id OAA14964 for ; Wed, 27 May 1998 14:39:45 -0300 (EST) Received: from coruja.dcc.unicamp.br (coruja.dcc.unicamp.br [143.106.24.80]) by amazonas.dcc.unicamp.br (8.8.5/8.8.5) with ESMTP id OAA21460 for ; Wed, 27 May 1998 14:39:44 -0300 (EST) Received: (from stolfi@localhost) by coruja.dcc.unicamp.br (8.8.5/8.8.5) id OAA14485; Wed, 27 May 1998 14:39:43 -0300 (EST) Date: Wed, 27 May 1998 14:39:43 -0300 (EST) Message-Id: <199805271739.OAA14485 [at] coruja [dot] dcc.unicamp.br> From: Jorge Stolfi To: reliable_computing [at] interval [dot] usl.edu Subject: Re: dependency problem Mime-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=iso-8859-1 In-Reply-To: <356BE714.52BF [at] mi [dot] leeds.ac.uk> References: <356BE714.52BF [at] mi [dot] leeds.ac.uk> Reply-To: stolfi [at] dcc [dot] unicamp.br Sender: owner-reliable_computing Precedence: bulk > [Zsuzsanna Szabo:] I would appreciate if someone could tell me > about methods for treating the dependency problem in interval > arithmetics (methods like affine arithmetics or > preconditioning). Affine arithmetic represents each quantity x as a sum x = x0 + x1*e1 + x2*e2 + ... + xn*en where the xi are floating-point numbers and the ei are symbolic variables (unknown, and not stored) assumed to range in [-1..+1]. This representation implies that x lies in the interval x* = [x0-r .. x0+r] where r = |x1| + |x2| + ... + |xn|; but it can also record partial correlations between quantities, so that (for example) x - x evaluates to exact 0, even if x has a non-trivial range. Non-linear operations f(x,y) on such "affine forms" boil down to selecting a good first-degree Chebyshev approximation of the operation f over the argument ranges x* and y*. The approximation and rounding errors of each operation are included as a new dummy variable ek (and so it has a chance of being canceled out in subsequent operations). Affine arithmetic resembles to some extent Hansen's generalized interval arithmetic; but there are some real differences. For one thing, in Hansen's model the coefficients are intervals too, so that x-x is not zero in general. Also, in Hansen's model the dummy variables ei are identified with the function's arguments; so it is not clear how one can represent correlations between the arguments, or keep track of the correlation data after the function returns; whereas in AA the dummy variables need not be attached to specific user variables, and retain their identity when crossing procedure boundaries. There are many other methods that are similar to AA, to the extent that all compute first-order (i.e. "affine") approximations to the desired quantities; which means that the truncation error decreases quadratically with the input size range. (In contrast, standard IA computes only a zero-order approximation for each quantity, and therefore has linear truncation error.) One well-known approach is to combine automatic differentiation and standard IA to obtain ranges for the function's derivatives (e.g. Matijasevich 1975). Another approach uses ellipsoids in general position that bound the graph of the quantity (eg. Kurzhanski, Chernousko, Ovseevich and others, 1994). The other approaches cited by G. Corliss seem to fall in this class, too, or use approximations of even higher order. You can find more details and the full references above at my AA site, http://www.dcc.unicamp.br/~stolfi/EXPORT/projects/affine-arith/ The most complete description of AA to date is Self-Validated Numerical Methods and Applications. by Luiz H. de Figueiredo and Jorge Stolfi. Brazilian Mathematics Colloquium monograph (108 pages), IMPA, Rio de Janeiro, Brazil; July 1997. http://www.dcc.unicamp.br/~stolfi/EXPORT/papers/ affine-arith/aa-97-07-val-num-book.ps.gz I now of a couple of implementations of AA freely available on the net. You can get mine (in C) from my site, above. I owe you pointers to others. I confess that I am not familiar enough with this field to compare AA against all other first-degree approximation schemas, such as the ones cited above. Our experience so far has been encouraging, and there is still plenty of room for improvement in our programs. However, as for all the first-degree approaches, there are also many problems where AA is not worth the extra cost; and we still can't tell offhand what are the the right problems for it. (I wish I could get a grad student interested in doing a thesis about AA, but they all would rather play with colored pictures than pore over long lists of 12-digit numbers. Perhaps I am in the wrong department... 8-() Hope it helps, --stolfi