March 2000 - Categories - categories.org.au

icalp2000-program and registration
by POWELL Olivier 31 Mar '00

31 Mar '00

ICALP' 2000 Program, Registration and Practical Information Sunday July 9th Registration Opens Late Afternoon -------------------------------------------------------------------= ----- Monday, July 10th 9:00 - 10:00 INVITED TALK Game Semantics: Achievements and Prospects Samson Abramsky 10:00 - 10:50 SESSION 1 Clique is hard to approximate within n*(1-o(1)) Lars Engebretsen, Jonas Holmerin Approximating the independence number and the chromatic number in expected polynomial time Michael Krivelevich, Van Vu -------------------------------------------------------------------= ----- 10:00 - 10:50 SESSION 2 Closed Types as a Simple Approach to Safe Imperative Multi-Stage Program Cristiano Calcagno, Eugenio Moggi, Walid Taha A Statically Allocated Parallel Functional Language Alan Mycroft, Richard Sharpu -------------------------------------------------------------------= ----- (Coffee Break 10:50 - 11:10) -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 1 An Optimal Minimum Spanning Tree Algorithm Seth Pettie, Vijaya Ramachandran Improved shortest paths on the word RAM Torben Hagerup Improved algorithms for finding level ancestors in dynamic trees Stephen Alstrup, Jacob Holm -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 2 Lax Logical Relations Gordon Plotkin, John Power, Donald Sannella, Robert Tennent Reasoning about Idealized Algol Using Regular Languages Dan R. Ghica, Guy McCusker The measurement process in domain theory Keye Martin -------------------------------------------------------------------= ----- (Lunch 12:30 - 14:30) -------------------------------------------------------------------= ----- 14:30 - 15:30 INVITED TALK Graph Transformation as Unifying Formal Framework for System Modeling and Model Evolution Gregor Engels 15:30 - 16:20 SESSION 1 Monotone Proofs of the Pigeon Hole Principle Albert Atserias, Nicola Galesi, Ricard Gavalda Homogenization and the Polynomial Calculus Josh Buresh-Oppenheim, Matt Clegg, Russell Impagliazzo, Toniann Pitassi -------------------------------------------------------------------= ----- 15:30 - 16:20 SESSION 2 Fully-abstract Statecharts Semantics via Intuitionistic Kripke Structures Gerald L=FCttgen, Michael Mendler Algebraic Models for Contextual Nets Roberto Bruni, Vladimiro Sassone -------------------------------------------------------------------= ----- (Coffee Break 16:20 - 16:40) -------------------------------------------------------------------= ----- 16:40 - 17:30 SESSION 1 Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems Beate Bollig, Ingo Wegener Measures of Nondeterminism in Finite Automata Juraj Hromkovic, Juhani Karhum=E4ki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert -------------------------------------------------------------------= ----- 16:40 - 17:30 SESSION 2 LTL is expressively complete for Mazurkiewicz traces Volker Diekert, Paul Gastin An automata-theoretic completeness proof for Interval Temporal Logic B. C. Moszkowski -------------------------------------------------------------------= ----- (Welcome reception 18:00) -------------------------------------------------------------------= ----- Tuesday, July 11th 9:00 - 10:00 INVITED TALK Which NP-hard optimization problems admit non-trivial efficient approximation algorithms? Johan Haastad 10:00 - 10:50 SESSION 1 Deterministic algorithms for k-SAT based on covering codes and local search Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Sch=F6ning Closest Vectors, Successive Minima and Dual HKZ-Bases of Lattices Johannes Bl=F6mer ----------------------------------------------------------------= ---- 10:00 - 10:50 SESSION 2 Variable Independence, Quantifier Elimination, and Constraint Representations Leonid Libkin Constraint Satisfaction Problems and Finite Algebras Andrei Bulatov, Andrei Krokhin, Peter Jeavons ----------------------------------------------------------------= ---- (Coffee Break 10:50 - 11:10) ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 1 An optimal online algorithm for bounded space variable-sized bin packing Steven S. Seiden Resource augmentation for online bounded space bin packing J=E1nos Csirik, Gerhard Woeginger Optimal projective algorithms for the list update problem Christoph Amb=FChl, Bernd G=E4rtner, Bernhard von Stengel ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 2 Efficient Verification Algorithms for One-Counter Processes Antonin Kucera On the Complexity of Bisimulation Problems for Basic Parallel Processes Richard Mayr Decidable first-order transition logics for PA-processes D. Lugiez, Ph. Schnoebelen ----------------------------------------------------------------= ---- (Lunch 12:30 - 14:30) ----------------------------------------------------------------= ---- 14:30 - 15:30 INVITED TALK Non Interference for Analysis of Cryptographic Protocols Roberto Gorrieri 15:30 - 16:20 SESSION 1 Average bit-complexity of Euclidean algorithms Ali Akhavi, Brigitte Vall=E9e Planar maps and Airy phenomena Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Mich=E8le Soria ----------------------------------------------------------------= ---- 15:30 - 16:20 SESSION 2 Analysing Input Output Capabilities of Mobile Processes with a Generic Type System Barbara K=F6nig Information Flow vs. Resource Access in the Information Asynchronous Pi-Calculus Matthew Hennessy, James Riely ----------------------------------------------------------------= ---- (Coffee Break 16:20 - 16:40) ----------------------------------------------------------------= ---- 16:40 - 17:40 AWARD TALK Past, Present and Future of TCS Richard Karp ----------------------------------------------------------------= ---- 17:40 EATCS General Assembly (Wine and cheese ) ----------------------------------------------------------------= ---- Wednesday, July 12th 9:00 - 10:00 INVITED TALK Alteration Verification Diagrams Zohar Manna 10:00 - 10:50 SESSION 1 Necessary and sufficient assumptions for non interactive zero knowledge proofs of knowledge for all NP relations Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano Computational PCP: Short one-round proofs for NP W. Aiello, S. Bhatt, R. Ostrovsky, S. Rajagopalan ----------------------------------------------------------------= ---- 10:00 - 10:50 SESSION 2 A New Unfolding Approach to LTL Model Checking Javier Esparza, Keijo Heljanko Reasoning about message passing in finite state environments B. Meenakshi, R. Ramanujam ----------------------------------------------------------------= ---- (Coffee Break 10:50 - 11:10) ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 1 Extended notions of security for multicast public key cryptosystems Olivier Baudron, David Pointcheval, Jacques Stern One-round secure computation and secure autonomous mobile agents Christian Cachin, Jan Camenisch, Joe Kilian, Joy M=FCller Round-optimal and abuse free multi-party contract signing Birgit Baum-Waidner, Michael Waidner ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 2 On the centralizer of a finite set Juhani Karhum=E4ki, Ion Petre On the power of tree-walking automata Frank Neven, Thomas Schwentick Determinization of transducers over infinite words Marie-Pierre B=E9al, Olivier Carton ----------------------------------------------------------------= ---- (Lunch 12:30 - 14:30) ----------------------------------------------------------------= ---- (City Tours and Excursion 14:30) ----------------------------------------------------------------= ---- Thursday, July 13th 9:00 - 10:00 INVITED TALK Graph Algorithms and Constraint Programming Kurt Mehlhorn 10:00 - 10:50 SESSION 1 Scalable secure storage when half the system is faulty Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern Dual-bounded hypergraphs: Generating partial and multiple transversals Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino ----------------------------------------------------------------= ---- 10:00 - 10:50 SESSION 2 Revisiting the correspondence between cut elimination and normalisation Jos=E9 Espirito Santo Negation Elimination from Simple Equational Formulae Reinhard Pichler ----------------------------------------------------------------= ---- (Coffee Break 10:50 - 11:10) ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 1 Hardness of set cover with intersection 1 V.S. Anil Kumar, Sunil Arya, H. Ramesh Strong inapproximability of the basic k-Spanner Problem Michael Elkin, David Peleg Approximating Minimum Spanning Sets in Hypergraphs and Polymatroids Gregor Baudis, Clemens Gr=F6pl, Stefan Hougardy, Till Nierhoff, Hans J=FCrgen Pr=F6mel ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 2 Infinite series parallel posets: logic and languages Dietrich Kuske On deciding if deterministic Rabin language is in Buchi class Tomasz Fryderyk Urbanski On Message Sequence Graphs and Finitely Generated Regular MSC Languages Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan ----------------------------------------------------------------= ---- (Lunch 12:30 - 14:30) ----------------------------------------------------------------= ---- 14:30 - 15:30 INVITED TALK Pseudorandomness Oded Goldreich 15:30 - 16:20 SESSION 1 A bound on the capacity of backoff and acknowledgement based protocols Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson Deterministic radio broadcasting Bogdan Chlebus, Leszek Gasieniec, Anna =D6stlin, John Michael Robson ----------------------------------------------------------------= ---- 15:30 - 16:20 SESSION 2 A Finite w-complete Equational Specification of Interleaving Wan Fokkink, Bas Luttik A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors Mario Bravetti, Roberto Gorrieri ----------------------------------------------------------------= ---- (Coffee Break 16:20 - 16:40) ----------------------------------------------------------------= ---- 16:40 - 17:30 SESSION 1 Tight size bounds for packet headers in narrow meshes Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson Wavelength assignment problem on all-optical networks with k fibres per link Luciano Margara, Janos Simon ----------------------------------------------------------------= ---- 16:40 - 17:30 SESSION 2 On the logical characterisation of performability properties Christel Baier, Boudewijn Haverkort, Holger Hermanns, Joost-Pieter Katoen On the Representation of Timed Polyhedra Olivier Bournez, Oded Maler ----------------------------------------------------------------= ---- (Conference dinner 20:00) ----------------------------------------------------------------= ---- -------------------------------------------------------------------= ----- Friday July 14th 9:00 - 10:00 INVITED TALK Min-wise Independent Permutations: Theory and Practice Andrei Broder 10:00 - 10:50 SESSION 1 Testing acyclicity of directed graphs in sublinear time Michael Bender, Dana Ron Computing the girth of a planar graph Hristo N. Djidjev -------------------------------------------------------------------= ----- 10:00 - 10:50 SESSION 2 Lower bounds are not easier over the reals: inside PH Herv=E9 Fournier, Pascal Koiran Unlearning helps Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan -------------------------------------------------------------------= ----- (Coffee Break 10:50 - 11:10) -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 1 Fast approximation schemes for Euclidean multiconnectivity problems Artur Czumaj, Andrzej Lingas Approximate TSP in graphs with forbidden minors Michelangelo Grigni Polynomial time approximation schemes for general multiprocessor job shop scheduling Klaus Jansen and Lorant Porkolab -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 2 The many faces of a translation Pierre McKenzie, Thomas Schwentick, Denis Th=E9rien, Heribert Vollmer Gales and the constructive dimension of individual sequences Jack Lutz The global power of additional queries to p-random oracles Wolfgang Merkle -------------------------------------------------------------------= ----- (Lunch 12:30 - 14:30) -------------------------------------------------------------------= ----- WORKSHOPS START AT 14:30 (* See individual workshop programs for schedule details.) -------------------------------------------------------------------= ----- Registration You may register electronically (opens in the begining of april) at t= he ICALP home page. The online registration application accepts MasterCa= rd, Visa and American Express cards. If you do not have one of these cred= it cards, or if you prefer not to register online, please download the registration form. Registration Fees Includes entrance to all sessions and workshops, a copy of the procee= dings, a copy of the workshops proceedings, luncheon, coffee breaks, social = events and the EATCS membership for one year. (1US=3D1.67CHF at the moment o= f the print) CHF 550.00 EATCS members registration received before June 1, 2000 CHF 650.00 Non EATCS members registration received before June 1, 2= 000 CHF 400.00 Student registration received before June 1, 2000 CHF 650.00 EATCS members registration after June 1, 2000 CHF 750.00 Non EATCS members registration after June 1, 2000 CHF 500.00 Student registration after June 1, 2000 CHF 150.00 Workshops only registration received before June 1, 2000 CHF 200.00 Workshops only registration after June 1, 2000 Practical Information -------------------------------------------------------------------= ----- -------------------------------------------------------------------= ----- Conference Site Universit=E9 de Gen=E8ve - UNI BASTIONS 3, place de l'Universit=E9 (at Rue de Candolle) Geneva How to get to Geneva Swissair and Crossair have been appointed official carrier for ICALP = '2000. To book the special conference fare, please contact your nearest Swis= sair office or, in the US and UK, the appointed travel agent listed below.= To obtain a discount fare, give the ticket agent the code SR IDS page GC= GRF C00-C26 and refer to the event as the 27th International Colloquium o= n Automata, Languages and Programming. The official Swissair designated airline ticketing agency is North American Participants: Conferences International, Inc. Toll Free in US and Canada 1-800-221-8747 Fax: 1-508-872-5566 United Kingdom Participants: Karen Hammond Tel 44-171-499-7611 Fax 44-171-493-0326 Participants from other countries should contact their nearest Swissa= ir office. If other arrangements including ground and rail are required, contact your travel agent for assistance. Accommodations In 2000, ICALP will be held in the old campus of the University of Ge= neva. The hotels listed below have reserved a block of rooms at special ICA= LP rates. The discounted rates offered by the Hotel du Midi, a very pres= tigious 4 star establishment, are an especially good value. Prices for the hotels are guaranteed but due to the high demand of ro= oms during the month of July in Geneva, register as early as possible to = assure your choice. The hotels are within 5-15 minutes walking distance from= the University of Geneva campus. To reserve accommodations, contact the selected hotel, preferably, by= fax and furnish the following information: Name - Affiliation - Address Phone and Fax Accommodations requested (Single/Double) Number in party (Ages of children) Arrival and Departure Date/Time Credit Card Guarantee (Most are accepted) Please cite: Special rate for the University of Geneva - ICALP 20= 00 NOGA HILTON GENEVE ***** CONTACT Mme Valerie Bonvin TEL +41 22 908-9193 FAX +41 22 908-9091 SINGLE CHF 330 DOUBLE CHF 380 HOTEL DU MIDI **** CONTACT Mme S. Ianna TEL +41 22 731-7800 FAX +41 22 731-0020 SINGLE CHF 140 DOUBLE CHF 180 HOTEL LE GRENIL *** CONTACT Mme Christine Hager TEL +41 22 328-3055 FAX +41 22 321-6010 SINGLE CHF 95 (breakfast included) DOUBLE CHF 130 (breakfast included) Other Accommodations For information and reservation of other accommodations and tour pack= ages, you or your travel agent may contact the Geneva Tourist Office. You c= an fax your data as above, any other relevant information and ask for a room reservation. Fax +41 22 909-7021 or call +41 22 909-7020 or write PO = Box 1602, CH-1211 Geneva 1, Switzerland. Also, take a look at their site = at http://www.geneve-tourisme.ch Alternatively, a limited number of very inexpensive rooms are availab= le at the Student Housing (Cit=E9 Universitaire). If you are interested in = such accomodations please contact icalp(a)cui.unige.ch Local Transportation >>From the airport: A taxi from the airport to either hotels or University will cost abou= t CHF 30. Alternatively you may take the train from the airport to the main= train station - a 5 minute walk from the first two hotels. The ride will co= st around CHF 5 and will take 10 minutes. Purchase a ticket before board= ing the train. >>From hotels to the University: It is a 10 minute walk from the first two hotels. You may cross the r= iver via either the Pont des Bergues or Pont de la Machine and then take R= ue de la Corraterie to Place Neuve. From the other hotel is a very short wa= lk, see the enclosed map. The University is located at the park called Promen= ade des Bastions. By public transportation, take tramway number 13 from the main train = station to the fourth stop (called Plainpalais). From there walk by rue du Co= nseil G=E8n=E8ral until you reach the Promenade des Bastions. Note: When using any local transportation, you need to purchase a tic= ket in advance at the machine located at the bus stop; the cost is CHF 2.20.= This ticket is valid for one hour and you may take as many connections as = you want. Also note that the machine does not give change, and if you ent= er a bus without a valid transportation ticket you risk being required to = pay a fine of about CHF 100 and a visit to the police station. Cuisine At ICALP '2000, luncheon will be served on the University campus to a= ll registrants on all five days and refreshments will be available durin= g breaks. On Thursday evening, there will be the official banquet of th= e conference. Please be sure to indicate on your registration form whet= her you prefer vegetarian meals. At other times, participants will have a broad choice of dining optio= ns offering international and gourmet fare all within walking distance o= f accommodations and many along the shores of Lake Geneva. The traditio= nal and most popular dishes among the local population are cheese fondue and raclette, delicious local wines, and lake perch. Currency and Credit Cards The unit of currency is the Swiss franc (CHF). Notes are issued in denominations of 10, 20, 50, 100, 200, and 1,000. Coins are issued in denominations of 5, 10, and 20 centimes, and .5, 1, 2, and 5 Swiss fr= ancs. At the moment of the print, 1US was worth CHF 1.67, but since this ra= te changes very often, check the real rate at the necessary moment. Most hotels, large stores, restaurants, and petrol stations accept all maj= or credit cards (American Express, MasterCard, Visa, Diners Club, Euroca= rd). Location Geneva is situated along the banks of Lac L=E9man (Lake Geneva) and L= e Rh=F4ne. The lake showcases the plumed fountain Jet d'Eau, and various distric= ts of Geneva are connected by bridges across the waterways. The University = of Geneva where ICALP '2000 will convene is located on the `Left Bank' o= ff Place Neuve and along the Promenade des Bastions near the Old Town se= ction of Geneva. The two first ICALP designated hotels (Noga and du Midi) are located lakeside - on the `Right Bank' - and are within walking distance of t= he University campus. It is a 10-15 minute walk which crosses through `O= ld Town'. Also, there is regular bus service running to the University, = so ICALP participants may come and go throughout the day. The Hotel Le G= renil and the University are both situated on the `Left Bank' and are very = close. Geneva is a city of water parks and gardens and welcoming walkways wh= ich encourage exploration of the historical sites, museums, and internati= onal business and shopping districts. The University of Geneva is located = near `Old Town' an area dotted with sidewalk cafes, student life, and buil= ding antiquities dating back to the 5th century. Geneva is a crossroads situated in the heart of Europe and linked to = the world by a vast network of motorways, airlines and railways. For thos= e planning to attend ICALP'2000 in Geneva, it is an excellent opportuni= ty to organize short trips into the countryside of charming villages and vineyards. Tours to please all ages and interests are available inclu= ding afternoon train excursions, shopping cruises on Lake Geneva and The R= hone, and bus and cablecar trips in the Alps. For some, the most inviting attraction will be mountain climbing. The= high mountains are situated less than half an hour drive from Geneva. In e= arly July, a very popular and almost mandatory activity is swimming in the= lake Geneva, so serious and not so serious swimmers should plan accordingl= y! Climate The climate in early July should be warm but still very pleasant with= nice evenings and breezes off the Lake. There may be showers but we can al= so expect sunny days. Passports and Visas A valid passport is required for entry into Switzerland. Some nationa= ls may also require a visa for Switzerland, and if you plan to visit France = one may be required there. Please check with your travel agent or consulate t= o determine whether a visa will be required.

1 0

unbounded choice
by Peter Freyd 30 Mar '00

30 Mar '00

Max and Mike both mentioned that there are addition-preserving self-maps on the reals that are unbounded on every non-trivial interval. But such examples require the axiom of choice. In a different context I happened to mention that just two months ago: Do we need the axiom of choice? If, instead, we add the axiom of measurability, then the counterexamples disappear: let f be a measurable midpoint-preserving map from R to R; we can easily specialize to the case that f0 = 0, hence f is a measurable group endomorphism; for any real a consider the induced group homomorphism from R/aZ to R/(fa)Z; any measurable group character is continuous and that's enough to force f to be continuous. (28 Jan) The example that Michael Wendt and I described (well, almost the same example) we didn't need choice but we did need -- as all good toponomers know -- the law of excluded middle for the equality predicate on the reals (in the category of spatial sheaves over a perfect space it is the case that all real-valued maps from a closed interval are, indeed, bounded.)

1 0

Functorial injective hulls
by Peter Freyd 30 Mar '00

30 Mar '00

Some comments on: >TITLE: Injective Hulls are not Natural >AUTHORS: J. Adamek, H. Herrlich, J. Rosicky and W. Tholen >ABSTRACT: In a category with injective hulls and a cogenerator, the >embeddings into injective hulls can never form a natural transformation, >unless all objects are injective. In particular, assigning to a field >its algebraic closure, to a poset or boolean algebra its MacNeille >completion, and to an R-module its injective envelope is not functorial, >if one wants the respective embeddings to form a natural transformation. What is meant by saying that an object is "injective" varies a bit from place to place. If it means that the object represents a contravariant functor that carries monics into epics and if one defines an "injective hull" of an object A to mean a monic A --> E where E is injective and such that A --> E --> X monic implies E --> X is monic then there are non-trivial examples of functorial injective hulls: take any poset with a top element and view it as a category; the only injective object is the top and the unique map from any object to the top is easily verified to be an injective hull. Apparently, therefore, the meaning of injective is a mutation obtained by changing the word "monic" in the above description to something stronger, such as "extremal monic" or "regular monic". (In Cats and Alligators the notions of projective and injective are not dual: a co-projective would be the mutation of injective obtained by using extremal monics.) If the strengthening of monic is such that it becomes an iso whenever epic (as is the case with extremal and regular), then there's an easy proof of the impossibility of functoriality, with or without a cogenerator. In the days when all categories were abelian (that is, in the days when people actually talked about injective hulls) it was also the case that all monic-epics were isos, and this easy proof was a pretty standard exercise. It goes as follows. Suppose that E is a functor, u a natural transformation from the identity functor to E such that u:A --> E(A) is an injective hull for all A. We wish to show that u is epic. If B is injective then there must be E(B) --> B such that B --> E(B) --> B is the identity map. The definition of injective hull forces E(B) --> B to be monic which, in turn, forces u_B to be an iso. We may replace E with a naturally equivalent functor with the property that u_B is the identity map whenever B is injective. For an arbitrary A consider u A ---> E(A) u | | E(u) 1 E(A) --> E(A) E(u) | | E(u) 1 E(A) --> E(A) and conclude that E(u) is an idempotent. Using again (and for the last time) the definition of injective hull we have that E(u) is monic. The only monic idempotent is the identity map. u x u y Suppose that A --> E(A) --> C = A --> E(A) --> C. Consider u u A ---> E(A) A ---> E(A) u | | 1 u | | 1 1 1 E(A) --> E(A) E(A) --> E(A) x | | E(x) y | | E(y) u u C ---> E(C) C ---> E(C) If one considers just the outer rectangles one sees that the left hand verticals are the same, hence so must be the right hand verticals. But u is monic, thus E(x) = E(y) implies x = y.

4 3

stupid question?
by M.M. Mawanda 30 Mar '00

30 Mar '00

I have been asked the following question: Is it true that any function defined in a real number closed interval [a,b] (there is not a hypothesis of continuity) is bounded in an open subinterval (c,d) of [a,b]? My spontaneous was NO. Unfortunately I cannot find a counter-example to disapproved my answer. Can someone help.

6 5

bounded = accessible
by Jiri Adamek 29 Mar '00

29 Mar '00

In the community investigating coalgebras of functors F: K-> K (i.e., comma-categories Id/F ) the following condition in case K = Set is quite often used: Definition: A set functor is called bounded if there exists a cardinal k such that for every element a of every coalgebra there exists a subcoalgebra of cardinality less than k containing a . ("Bounded at k " is used for the given k.) So I wondered how this is related to accessibility, and here is the answer: Proposition: A set functor is bounded iff it is accessible. In fact, if k is an infinite, regular cardinal, then k-accessible = bounded at k . For, suppose that F is bounded at k , then we prove that in the usual category of elements of F for every object (A,a) there exists a morhpism m: (B,b) -> (A,a) with card B < k . It then follows easily that F is k-accessible (see e.g. 2.17 in the book of Rosicky and myself). We can assume A nonempty, and choose x in A. Let p:A -> FA be the coalgebra given by the constant map to a . There exists a subcoalgebra m: (B,q) -> (A,p) for some q: B -> FB with card B < k such that x = m(y) for an element y of B . Then b = q(y) clearly fulfills a = Fm(b), as requiered. Conversely, suppose that F is k-accessible. Given a coalgebra p: A -> FA , consider the collection m_i: A_i -> A of all subsets of cardinality less than k . Since F preserves k-directed unions, for each i there exists an i' such that m_i is contained in m_i' and the image of p.m_i is contained in that of Fm_i' . After iterating i -> i' -> (i')' ... k times we find a j such that m_i is contained in m_j , and the image of p.m_j is contained in that of Fm_j. The latter means that p can be restricted to p_j: A_j -> FA_j forming a subcoalgebra of the coalgebra above. Since every element of FA is contained in the image of some Fm_i , this proves that F is bounded at k . xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx alternative e-mail address (in case reply key does not work): J.Adamek(a)tu-bs.de xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

1 0

PhD places at LFCS
by Ian.Stark＠ed.ac.uk 27 Mar '00

27 Mar '00

PhD positions available for October 2000 Laboratory for Foundations of Computer Science Division of Informatics, University of Edinburgh Applications are open for students to take up PhD places at Edinburgh in October 2000. Supporting funds are available for postgraduates of any nationality. The Laboratory for Foundations of Computer Science is one of the world's leading centres of research into theoretical computer science and its application. An important part of this is its active community of research students, currently over 20 strong. LFCS runs a 3-year PhD programme; this includes a series of taught courses which provide a broad background in the theory of computation, and prepare students to do their own research work. All students are directly supervised by an academic staff member. The Laboratory and the Division fund some studentships of their own, open to applicants of any nationality. UK students can also apply for one of several grants awarded to the Division by the EPSRC. For more information, including details of how to apply, please consult our web site. http://www.lfcs.informatics.ed.ac.uk/research/students.html -------------------------------------------------------------------- Ian Stark Deputy Director, LFCS http://www.lfcs.informatics.ed.ac.uk

1 0

Re: Functorial injective hull.
by mbatanin＠ics.mq.edu.au 27 Mar '00

27 Mar '00

This is just to give different point of view to the problem. 1. Suppose we have a category C and a full subcategory H (think of H as a subcategory of injective objects). Suppose we have a functor E:C --> H together with natural transformation i: Id --> E(C) such that i is monic and ,moreover, E is weak left adjoint to the inclusion functor H --> C. Then I claim that under two additional conditions E is genuine adjoint and i is unit of the adjunction. The conditions are: a. the natural transformation i is identity on H. b. E preseves monics. The proof is just a repetition of P.Freyd proof. We have to prove that the extension in the diagram i:A --> E(A) | / f | / | / I is unique for any morphism f and "injective" I. By applying E to this diagram and using condition a) we see that it is sufficient to prove that E(i) is identity. Repeating Freyd's proof we see that E(i) is idempotent. Using condition b) we conclude that it is identity. The conditions a) and b) are obviously satisfied in the case when E is "injective hull functor" (of coarse a) is true up to iso, again see P,Freyd proof). As the unit of the adjunction is monic so the functor E reflects epimorphisms. If in C we have that mono + epi implies iso we finally have that i is iso and ,hence, the result of Adamek, Herrlish, Rosicky and Tholen. 2. I would not dare to simply repeat P.Freyd argument if I don't have another proof (in a special but important case). The proof is much more techniqual but I believe reflects another interesting side of the problem of functoriality of injective resolutions. Consider the following bicategory. The objects are categories enriched in the closed monoidal category of (say bounded ) chain complexes. The 1-arrows are enriched distributors. The 2-arrows are homotopy classes of "coherent" natural transformations (i.e. we localize the category of natural transformations with respect to the class of morphisms which are level quaziisomorphisms). We have to define the composition of 1-arrows. This requires some techniques but in a few words the result is left derived functor of the composition of enriched distributors. The resulting bicategory is closed on the left and right. Now, for a chain functor K: A --> B we can consider the right Kan extension of it along itself in the above bicategory (codensity monad). The Kleisli category of it is called "strong shape theory of K" Ssh_K. It is possible to prove, that: c). If K is a full embedding and has an enriched left adjoint then Ssh_K is just a Kleisli category of the corresponding monad on B. d). If B is the category of chain complexes (say bounded)in an abelian category with enough injectives and A is full subcategory of injective chain complexes, then homology of Ssh_K(X,Y) are isomorphic to the right derived functor of internal Hom of B. In particular, if X and Y are concentrated in the dimension 0 the cohomology are just the correspobding Ext's. Coming back to the original problem. If H\in C are abelian and satisfy the conditions a),b) then, according to our calculations the inclusion K: Ch(H) ---> Ch(C) has a right adjoint and , hence,(by point c) Ssh_K(X,Y) = Hom(X,E(Y)) for X,Y concentrated in dimension 0. Hence by d) the injective dimension of C is 0 and we have the result again. Another words the injective dimension is the obstruction for nonnaturality of the injective hull. The same sort of theory can be developed for simplicial (or Cat) enriched situation see Batanin.M, Categorical Strong Shape THeory, Cahiers de Topologie et Geom, v,XXXVIII-1(1997)p. 3-66. I think some other results of nonaturality (as , for example, the result of Shakhmatov mentioned by AHRT on p.8) are related to these strong shape categories. Michael Batanin.

1 0

Re: More comments on Functorial injective hulls
by Walter Tholen 25 Mar '00

25 Mar '00

Good point, I did not see that! So the whole thing boils down to a very simple observation on pointed endofunctors (which is certainly well-known for reflectors): suppose you have an endofunctor F and a natural transformation u:Id --> F which is pointwise monic; then, if Fu is pointwise epic, u itself is pointwise epic. Proof: u_A x,y A ---> FA ---> B | | | u_A | u_FA | | u_B | | | FA --> FFA --> FB Fu_A Fx,Fy ( xu = yu gives Fx.Fu = Fy.Fu, hence Fx = Fy and then ux = uy and x = y.) Coming back to injectivity: if u was pointwise an H-injective hull, then both uF and Fu must be isos (independently of H being a class of monos or not!). Hence, if H is a class of monos, the statement above applies. > Walter wrote "We are able to compensate for the loss of mono through > condition 1". Wouldn't it be simpler just to say that condition 1 > implies that everything in H is a monomorphisms? > x y > (Let A --> B be an H-morphism and let X --> A, X --> A be such > x y > that X --> A --> B = X --> A --> B. If x were different from > y then there would be A --> E, E an H-injective object, so that > x y > X --> A --> E were different from X --> A --> E. But there would > have to be B --> E such that A --> E = A --> B --> E and > x y > X --> A --> B would have be different from X --> A --> B.) > > > So H-morphism is a strengthening of monic and that put's us back to > the situation I outlined: > > If the strengthening of monic is such that it becomes an iso > whenever epic then there's an easy proof of the impossibility of > functoriality, with or without a cogenerator. > >-- End of excerpt from Peter Freyd

1 0

Job Ad: Fwd: Daily SMARTS Output - 1 hit(s)
by Ross Street 24 Mar '00

24 Mar '00

>**************************************** >Sponsor: Monash University >Program Number: 38904 >Title: Monash University--Logan Research Fellowships >E-mail: MaryJoy.Gleeson(a)adm.monash.edu.au >Web Site: http://www.monash.edu.au/resgrant/loganfs > >SYNOPSIS: > Five prestigious fellowships are awarded each year to applicants >with two to six years of postdoctoral research experience. The >appointment is for three years, extendible to six years, to be taken >up by 31 December 2000. The initial salary is in the range >A$53,844-$57,464 pa depending on experience and a Research Support >Grant ranges from A$5,000-$20,000 pa. Return airfares are provided for >candidates and their dependents. > >Deadline(s): 28/04/2000 >Link to full program description: >http://australia.infoed.org/wConnect/wc.dll?spinwww~program~38904~BD

1 0

AMAST 2000 Call for Participation
by Teodor Rus 24 Mar '00

24 Mar '00

The advance program of the AMAST 2000 is now available on the web at the URL http://www.cs.uiowa.edu/amast2000. We hope that this program is inciting and exciting for you and consequently you will decide to attend this conference. Teodor Rus

1 0