February 1995 - Categories - categories.org.au

APCS questionnaire form
by Dr. P.T. Johnstone 06 Mar '95

06 Mar '95

The following is the (slightly amended) text of an e-mail message I have just sent to Paula Sonneveld at Kluwer Academic Publishers. It should be self-explanatory. If you agree with me about the questionnaire form, please send a message to Ms Sonneveld (paula.sonneveld(a)wkap.nl) saying so---it is only by concerted action that we can check the spread of this bureaucratic nonsense. Peter Johnstone ___________________________________________________________________ Dear Ms Sonneveld, I have just sent you a report on paper no. (deleted) by (name deleted), which you asked me to referee for the journal `Applied Categorical Structures'. Having refereed several papers for this journal, I am becoming increasingly irritated by the questionnaire form which you send out with every paper. Several of the questions on this form are invariably irrelevant to mathematical papers, and those that do have some relevance are almost always impossible to answer with a straight `yes' or `no'---the only sensible answer is `read my detailed report'. So it seems to me that the questionnaire is a complete waste of time and paper. I therefore wish to inform you that, although I remain entirely willing to referee papers for `Applied Categorical Structures', I shall in future ignore any papers which you send to me accompanied by this questionnaire. I further intend to publicize this decision via the `Categories' electronic mailing list, and to urge other category-theorists who have refereed for APCS and who agree with me about the uselessness of this form to take the same action. Yours sincerely, Peter Johnstone

5 5

Composition as a relation?
by David Espinosa 04 Mar '95

04 Mar '95

Has there been any work on "categories" with composition as a relation instead of a function? We would allow several "composites" of two arrows but would likely require unique composition with the identity: f o id = {f} David

3 4

Research Fellowships at QMW
by Edmund Robinson 24 Feb '95

24 Feb '95

Please bring these research fellowships to the notice of anyone you think might be interested. all best wishes Edmund Robinson -------------------------------------------------------------------- Department of Computer Science Queen Mary & Westfield College University of London ADVANCED / SENIOR RESEARCH FELLOWSHIPS As an important part of our strategy to accelerate research activity in this highly-rated research department we wish to appoint a small number of full-time Research Fellows in Computer Science. The fellowships will be of one to two years duration and are aimed at experienced researchers who would benefit from collaborating with staff at QMW in a lively and well resourced research setting. The department (rated 4A in the last research selectivity exercise) has strong well resourced research groups in several mainstream areas of computer science including; artificial intelligence; computer graphics and virtual reality; distributed and parallel systems; human computer interaction, programming and the theory of computation. Applicants for an Advanced Fellowship (Ref: 95034) should have a PhD in a relevant area of computer science together with a minimum of two years research experience and sound publication record providing evidence of potential to lead research. Salary will be in the range 16,075 - 23,087 pounds. Applicants for a Senior Research Fellowship (Ref: 95035) must have a minimum of five years research experience since obtaining their PhD in a relevant area of computer science together with an excellent publication record providing evidence of a significant contribution to their chosen area of computer science and proven ability to lead research. Salary will be in the range 26511 - 32665 pounds. For informal discussions contact Mel Slater (mel(a)dcs.qmw.ac.uk) (0171 975 52..) further information about the department can be found on World Wide Web: http://www.dcs.qmw.ac.uk/ For an application form and further details, please telephone our 24 hour Recruitment Line on 0171 975 5171, quoting the relevant Reference Number. Completed applications forms should be returned by 14th March 1995 to the Recruitment Coordinator, Personnel Office, Queen Mary and Westfield College, Mile End Road, London E1 4NS. ------------------------------------------------------------- This announcement is also available on World Wide Web: http://www.dcs.qmw.ac.uk/~mel/Admin/fellowad.html

1 0

Appointment
by ajp＠dcs.ed.ac.uk 24 Feb '95

24 Feb '95

Dear Colleagues, It gives me great pleasure to announce that Edmund Robinson has accepted a full professorship in the Computer Science Department of the Queen Mary and Westfield College of the University of London. It is one of the best Computer Science departments in Britain. Peter Landin is there, as is David Pym, and I believe Samson Abramsky received his doctorate there. With best wishes, John Power.

1 0

FinLim et FinProd ?
by Monique Mathieu 23 Feb '95

23 Feb '95

Lors des Journees d'Etude sur les Esquisses du 6 et 7 fevrier, organisees a Paris 7, j'ai ete sollicitee pour parler sur le theme " esquissabilite et monadicite ". J'ai relu differents textes a cette occasion et j'ai notamment trouve une construction tres naturelle de l'esquisse des categories a limites choisies, construction qui demontre de plus la monadicite de cette categorie sur Cat. Recemment, on m'a montre le texte de Atish Bagchi et Charles Wells : " Graph-based Logic and Sketches I : The General Framework ". Je trouve ce texte fort bien ecrit mais complique, notamment la construction des esquisses de categories a produits ou limites choisis (FinProd et FinLim), sans comprendre la raison de cette complication. Quelqu'un peut-il m'expliquer l'interet (cache) de cette complication ? Je peux, bien sur, envoyer a quiconque me le demandera mes references, voire un resume, en anglais si necessaire, de la construction que j'annonce. Cordialement. Monique Mathieu.

1 0

course on categories available
by Jaap van Oosten 21 Feb '95

21 Feb '95

I wrote a first course in category theory which I think more or less contains what's presumed knowledge in not too specialized papers and thesises (in computer science). It's 75 pages. The synopsis is: 1. Categories and functors. Definitions and examples. Duality principle. 2. Natural transformations. Exponents in Cat. Yoneda lemma. Equivalence of categories; Set^{op} equivalent to Complete Atomic Boolean Algebras. 3. Limits and Colimits. Functors preserving (reflecting) them. (Finitely) complete categories. Limits by products and equalizers. 4. A little piece of categorical logic. Regular categories, regular epi-mono factorization, subobjects. Interpretation of coherent logic in regular categories. Expressing categorical facts in the logic. Example of \Omega -valued sets for a frame \Omega. 5. Adjunctions. Examples. (Co)limits as adjoints. Adjoints preserve (co)limits. Adjoint functor theorem. 6. Monads and Algebras. Examples. Eilenberg Moore and Kleisli as terminal and initial adjunctions inducing a monad. Groups monadic over Set. Lift and Powerset monads and their algebras. Forgetful functor from T-Alg creates limits. 7. Cartesian closed categories and the \lambda-calculus. Examples of ccc's. Parameter theorem. Typed \lambda calculus and its interpretation in ccc's. Ccc's with natural numbers object: all primitive recursive functions are representable The notes are available by anonymous ftp via: ftp ftp.daimi.aau.dk cd pub/BRICS/LS/95/1 get BRICS-LS-95-1.ps.gz Jaap van Oosten

1 0

Faculty positions of potential interest to <<categories>> readers
by David B. Benson 19 Feb '95

19 Feb '95

Faculty Positions in Computer Science School of Electrical Engineering and Computer Science Washington State University The School of Electrical Engineering and Computer Science solicits applications for a permanent computer science faculty position at the Assistant Professor level. Responsibilities include initiation and supervision of research programs and instruction at undergraduate and graduate levels. Applicants should have an earned PhD degree in Computer Science or in a closely related field by Fall 1995. We seek outstanding and accomplished candidates in specific areas of computer science which include computer systems, software engineering, database systems, networks and distributed systems. Screening of applications will begin on March 15 and continue until the position is filled. Position starts on August 15, 1995. The School of Electrical Engineering and Computer Science solicits applications for a permanent computer science faculty position at Associate or Full Professor level. Responsibilities include initiation and supervision of research programs and instruction at undergraduate and graduate levels. Applicants should have an earned PhD degree with proven records of accomplishment in their fields as evidenced by sponsored research programs and publications. We seek outstanding and accomplished candidates in specific areas of computer science which include software engineering, specification and verification, operating systems, database systems, and other related software areas. Screening of applications will begin on December 15 and continue until the position is filled. Position start on August 15, 1995. ----------------- Washington State University has offered the Ph.D. in computer science since 1970, and also offers B.S. and M.S. degrees. The School of EECS has over forty faculty (approximately fifteen with primary interests in computer science and engineering), sixty computer science graduate students, and active research groups devoted to parallel and distributed processing, imaging (computer graphics, visualization, image processing, and vision), artificial intelligence, neural networks, and other areas. Computing facilities in the School of EECS include PCs, graphics workstations, and servers, all with Internet access. WSU has about 17,000 students and is located in Pullman, a quiet university town in the southeast corner of the state (approximately 75 miles south of Spokane). Nearby are some of the nation's most pristine and uncrowded places for outdoor recreation. The Pullman school system is widely acknowledged to be one of the very finest in the Pacific Northwest. ! Applicants should send a cover letter, a curriculum vita, and the names and ! addresses of three references qualified to comment on their research and ! teaching qualifications to ! ! Chair, Computer Science Search Committee ! School of Electrical Engineering and Computer Science ! Washington State University ! Pullman, WA 99164-2752 WSU is an EO/AA educator and employer. Protected group members are encouraged to apply.

1 0

LICS'95 Accepted Papers
by Amy Felty 14 Feb '95

14 Feb '95

Day 1 ===== Program Logics -------------- Completeness of Kozen's Axiomatisation of the Propositional $\mu$-Calculus, Igor Walukiewicz Once and For All, Orna Bernholtz, Amir Pnueli Complete Proof Systems for First Order Interval Temporal Logic, Bruno Dutertre Finite Models I --------------- The Infinitary Logic of Sparse Random Graphs, James F. Lynch, Jerzy Tyszkiewicz Generalized Quantifiers and 0-1 Laws, Anuj Dawar, Erich Gr\"{a}del Relativized Logspace and Generalized Quantifiers over Finite Structures, Georg Gottlob First-order Queries on Finite Structures over the Reals, Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht Model Checking and Verification ------------------------------- Model-Checking of Causality Properties, Rajeev Alur, Doron Peled, Wojciech Penczek On the Complexity of Modular Model Checking, Moshe Y. Vardi Timing Behavior Analysis for Real-Time Systems, Farn Wang On the Verification Problem of Nonregular Properties for Nonregular Processes, Ahmed Bouajjani, Peter Habermehl, Rachid Echahed Day 2 ===== Theorem Proving and AI ---------------------- Uniform Proofs and Disjunctive Logic Programming, Gopalan Nadathur, Donald W. Loveland Structural Cut Elimination, Frank Pfenning Paramodulation without Duplication, Christopher Lynch Complexity of Normal Default Logic and Related Modes of Nonmonotonic Reasoning, V. Wiktor Marek, Anil Nerode, Jeffrey B. Remmel Concurrency I ------------- Control Structures, Alex Mifsud, Robin Milner, John Power Configuration Structures, R. J. Van Glabbeek, G. D. Plotkin A Typed Calculus of Synchronous Processes, Simon Gay, Rajagopal Nagarajan Modal $\mu$-Types for Processes, Marino Miculan, Fabio Gadducci Semantics I ----------- Games and Full Abstraction for the Lazy $\lambda$-Calculus, Samson Abramsky, Guy McCusker Games Semantics for Full Propositional Linear Logic, Fran\c{c}ois Lamarche A Fully Abstract Semantics for a Concurrent Functional Language with Monadic Types, Alan Jeffrey Day 3 ===== Lambda-Calculus and Types ------------------------- Equality Between Functionals in the Presence of Coproducts, Daniel J. Dougherty, Ramesh Subrahmanyam A Logic of Subtyping, Giuseppe Longo, Kathleen Milsted, Sergei Soloviev Normalization and Extensionality, Adolfo Piperno New Notions of Reduction and Non-Semantic Proofs of $\beta$-Strong Normalization in Typed $\lambda$-Calculi, A. J. Kfoury, J. B. Wells Finite Models II ---------------- Finitely Monotone Properties, Alexei P. Stolboushkin Tree Canonization and Transitive Closure, Kousha Etessami, Neil Immerman Ptime Canonization for Two Variables with Counting, Martin Otto When Do Fixed Point Logics Capture Complexity Classes?, Anil Seth Unification and Rewriting ------------------------- Higher-Order Unification via Explicit Substitutions, Gilles Dowek, Th\'{e}r\`{e}se Hardin, Claude Kirchner Sequentiality, Second Order Monadic Logic and Tree Automata, Hubert Comon Orderings, AC-Theories and Symbolic Constraint Solving, Hubert Comon, Robert Nieuwenhuis, Albert Rubio Day 4 ===== Model Checking II ----------------- Efficient On-the-Fly Model Checking for $CTL^{*}$, Girish Bhat, Rance Cleaveland, Orna Grumberg Partial Model Checking, Henrik Reif Andersen Hardware Verification via Boolean Logic Programming, Enrico Tronci Concurrency II -------------- Compositionality via Cut-Elimination: Hennessy-Milner Logic for an Arbitrary GSOS, Alex K. Simpson Compositional Testing Preorders for Probabilistic Processes, Bengt Jonsson, Wang Yi Semantics II ------------ The Stone Gamut: A Coordinatization of Mathematics, Vaughan R. Pratt Logically Presented Domains, Erik Palmgren, Viggo Stoltenberg-Hansen Domain Theory in Stochastic Processes, Abbas Edalat Linear Logic ------------ Decision Problems for Second Order Linear Logic, Patrick Lincoln, Andre Scedrov, Natarajan Shankar The Complexity of Neutrals in Linear Logic, Max I. Kanovich Decidability of Linear Affine Logic, Alexei P. Kopylov

1 0

Summer School on Semantics and Logic of Computation
by Andrew Pitts 14 Feb '95

14 Feb '95

A Newton Institute Summer School SEMANTICS AND LOGICS OF COMPUTATION 25--29 September 1995 Newton Institute, Cambridge, UK in collaboration with the ESPRIT CLICS-II project Call for Registration The Summer School on Semantics and Logics of Computation is being held as part of a six-month research programme on Semantics of Computation at the Isaac Newton Institute for Mathematical Sciences, a new international research centre in Cambridge UK. The Summer School is sponsored by the CEC ESPRIT research project "Categorical Logic in Computer Science, II" (CLICS-II). The aim is to present a number of modern developments in semantics and logics of computation in a way that is accessible to graduate-level students. Registrations from postgraduate students will be given priority, but applications by interested academics and industrialists are also welcomed. The planned courses include: Samson Abramsky (Imperial) on "Semantics of interaction" Thierry Coquand (Chalmers) on "Computational content of classical logic" Martin Hofmann (Edinburgh) on "Dependent type theory: syntax, semantics, and applications" Martin Hyland (Cambridge) on "Game Semantics" Eugenio Moggi (Genova) on "Computational types and applications" Mogens Nielsen & Glynn Winskel (Aarhus) "Models for concurrency" Andrew Pitts (Cambridge) "Operationally-based theories for proving program properties" ORGANIZERS: For CLICS-II: Peter Dybjer (Chalmers) peterd(a)cs.chalmers.se For the NIMS Semantics of Andrew Pitts (Cambridge) Computation Programme: ap(a)cl.cam.ac.uk LOCATION: The workshop will take place in the Newton Institute's purpose-designed building, in a pleasant area in the west of Cambridge, about one mile from the centre of the City. Accommodation for participants will be provided next door to the Newton Institute in the study bedrooms of Girton College's Wolfson Court. The accommodation will be available from the evening of Sunday 24 September until the morning of Saturday 30 September. FEES: general rate: 400 pounds student rate: 250 pounds The fee covers registration, accommodation, meals (breakfast, lunch, supper, tea & coffee breaks), and lecture materials. REGISTRATION: There are only a limited number of places available on the Summer School. Intending participants are advised to apply for registration as soon as possible, and in no case later than 31 May 1995. To apply, please send your name and address (including e-mail or fax number, if available) to: Florence Leroy (SEM Summer School) Isaac Newton Institute 20 Clarkson Road Cambridge CB3 0EH Tel: +44 1223 335984 Fax: +44 1223 330508 Email: f.leroy(a)newton.cam.ac.uk IMPORTANT DATES: Deadline for registration 31 May 1995 Arrival date 24 September 1995 Scientific programme 25--29 September 1995 Departure date 30 September 1995 ---------------------------------------------------------------------------

1 0

actes de CAEN 94
by Pierre Ageron 10 Feb '95

10 Feb '95

(* This is to announce that the proceedings of the C.A.E.N. workshop, which was held in September 1994, will soon be available to everybody who is interested *) Les actes des journees CAEN 94 (Categories, Algebres, Esquisses, Neo-esquisses) seront disponibles en principe a la fin du mois de fevrier 1995. Ils comprennent des contributions originales, soigneusement relues et corrigees, des auteurs suivants : DEHORNOY, PORTER, DUVAL et REYNAUD, LAFONT, JOHNSTONE, DRECKMANN, VAN DE WIELE, GERNER et GUITART, GUITART, DAMPHOUSSE et GUITART, GORDON et POWER, SENECHAUD, LELLAHI, BOURN, AGERON, BURRONI et PENON, WEHRUNG, BROWN, MATHIEU, LAIR, RETORE, STELL. La plupart de ces articles sont en francais, les autres sont en anglais; ils totalisent 142 pages. Le volume d'actes sera envoye gratuitement a chaque personne qui en fait la demande, ceci dans la limite du tirage prevu (un seul exemplaire par personne ou bibliotheque). Il suffit pour cela de m'envoyer votre commande par la poste, en indiquant clairement l'adresse a laquelle il devra etre expedie. Les commandes faites par courrier electronique ne seront pas prises en compte. Les auteurs n'ont bien evidemment pas a passer commande. Pierre AGERON Departement de Mathematiques Universite de Caen 14032 CAEN Cedex FRANCE

1 0