April 2008 - Categories - categories.org.au

Foundations?
by F W Lawvere 03 Sep '10

03 Sep '10

Down with "Foundations"! Up with algebra! Dear Friends, Presumably I am among those who are being "vilified" as "lovers of categories as foundation". By avoiding any precise definition, such a formulation might appeal to the widespread justified boredom induced by the past hundred years of "foundations as justification". Whenever I used the word "foundation" in my writings over the past forty years, I have explicitly rejected that reactionary use of the term and instead used the definition implicit in the work of my teachers Truesdell and Eilenberg. Namely, an important component of mathematical practice is the careful study of historical and contemporary analysis, geometry, etc. to extract the essential recurring concepts and constructions; making those concepts and constructions (such as homomorphism, functional, adjoint functor, etc.) explicit provides powerful guidance for further unified development of all mathematical subjects, old and new. What is the primary tool for such summing up of the essence of ongoing mathematics? Algebra! Nodal points in the progress of this kind of research occur when, as is the case with the finite number of axioms for the metacategory of categories, all that we know so far can be expressed in a single sort of algebra. I am proud to have participated with Eilenberg, Mac Lane, Freyd, and many others, in bringing about the contemporary awareness of Algebra as Category Theory Had it not been for the century of excessive attention given to the alleged possibility that mathematics is inconsistent, with the accompanying degradation of the F-word, we would still be using it in the sense known to the general public: the search for what is "basic". We, who supposedly know the explicit algebra of homomorphisms, functionals, etc. are long remiss in our duty to find ways to utilize those concepts also in guiding high school calculus. Best wishes, Bill Bibliography: - The Category of Categories as a Foundation for Mathematics, La Jolla conference 1965, Springer (1966) - Adjointness in Foundations, Dialectica, (1969), to be reprinted in TAC - Foundations and Applications: Axiomatization and Education, Bulletin of Symbolic Logic, (2003) vol 9, pp 213-224 - Sets for Mathematics, w/ Bob Rosebrugh, Cambridge Univ. Press, (2003) ************************************************************ F. William Lawvere Mathematics Department, State University of New York 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA Tel. 716-645-6284 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere ************************************************************

2 1

WoLLIC 2008 - Call for Participation
by ruy＠cin.ufpe.br 28 Apr '08

28 Apr '08

[** sincere apologies for duplicates **] Call for Participation 15th Workshop on Logic, Language, Information and Computation (WoLLIC 2008) http://wollic.org/wollic2008/ Heriot-Watt University Edinburgh, Scotland July 1-4, 2008 >>>>>> SPECIAL: There will be a screening of George Csicsery's "JULIA ROBINSON AND HILBERT'S TENTH PROBLEM" http://zalafilms.com/films/juliarobinson.html with kind permission of the film director WoLLIC is an annual international forum on inter-disciplinary research involving formal logic, computing and programming theory, and natural language and reasoning. Each meeting includes invited talks and tutorials as well as contributed papers. The Fifteenth WoLLIC will be held in the campus of Heriot-Watt Univ, Edinburgh, Scotland, from July 1 to July 4, 2008. It is sponsored by the Association for Symbolic Logic (ASL), the Interest Group in Pure and Applied Logics (IGPL), the European Association for Logic, Language and Information (FoLLI), the European Association for Theoretical Computer Science (EATCS), the Sociedade Brasileira de Computacao (SBC), and the Sociedade Brasileira de Logica (SBL). SCIENTIFIC PROGRAMME Research contributions will be presented on all pertinent subjects, with particular emphasis in cross-disciplinary topics: foundations of computing and programming; novel computation models and paradigms; broad notions of proof and belief; formal methods in software and hardware development; logical approach to natural language and reasoning; logics of programs, actions and resources; foundational aspects of information organization, search, flow, sharing, and protection. INVITED SPEAKERS Olivier Danvy (BRICS) Anuj Dawar (Cambridge, UK) Makoto Kanazawa (Nat Inst of Informatics, Japan) Sam Lomonaco (U Maryland Baltimore) Mark Steedman (Edinburgh U) Henry Towsner (CMU) Nikolay Vereshchagin (Moscow) PROGRAMME COMMITTEE Lev Beklemishev (Utrecht) Eli Ben-Sasson (Technion) Xavier Caicedo (U Los Andes, Colombia) Mary Dalrymple (Oxford) Martin Escardo (Birmingham) Wilfrid Hodges (Queen Mary, U London) (Chair) Achim Jung (Birmingham) Louis Kauffman (Maths, U Ill at Chicago) Ulrich Kohlenbach (Darmstadt) Leonid Libkin (Edinburgh U) Giuseppe Longo (Ecole Normal Superieure, Paris) Michael Moortgat (Utrecht) Valeria de Paiva (PARC, USA) Andre Scedrov (Maths, U Penn) Valentin Shehtman (Inst for Information Transmission Problems, Moscow) Joe Wells (Heriot-Watt U, Scotland) ORGANISING COMMITTEE Mauricio Ayala-Rincon (U Brasilia, Brazil) Fairouz Kamareddine (Heriot-Watt U, Scotland, co-chair) Anjolina de Oliveira (U Fed Pernambuco, Brazil) Ruy de Queiroz (U Fed Pernambuco, Brazil, co-chair) STEERING COMMITTEE S. Abramsky, J. van Benthem, J. Halpern, W. Hodges, D. Leivant, A. Macintyre, G. Mints, R. de Queiroz WEB PAGE wollic.org/wollic2008/ INVITED TALKS Inter-Deriving Semantic Artifacts for Object-Oriented Programming Olivier Danvy and Jaco Johannsen On the Descriptive Complexity of Linear Algebra Anuj Dawar Talks on Quantum Computing Sam Lomonaco On game semantics of the affine and intuitionistic logics Ilya Mezhirov and Nikolay Vereshchagin CONTRIBUTED TALKS Conjunctive Grammars and Alternating Pushdown Automata Tamar Aizikowitz and Michael Kaminski Expressive Power and Decidability for Memory Logics Carlos Areces, Diego Figueira, Santiago Figueira and Sergio Mera Reasoning with Uncertainty by Nmatrix-Metric Semantics Ofer Arieli and Anna Zamansky A Propositional Dynamic Logic for CCS Programs Mario Benevides and Luis Menasche Schechter Towards Ontology Evolution in Physics Alan Bundy and Michael Chan Interval Additive Generators of Interval T-Norms Gracaliz Dimuro, Benjamin Bedregal, Renata Reiser and Regivan Nunes PDL as a Logic of Belief Revision Jan van Eijck and Yanjing Wang Time Complexity and Convergence Analysis of Domain Theoretic Picard Method Amin Farjudian and Michal Konecny Matching and Alpha-Equivalence for Nominal Terms with Variables and Permutations Christophe Calves and Maribel Fernandez On the formal semantics of IF-like logics Santiago Figueira, Daniel Gorin and Rafael Grimson On a graph calculus for algebras of relations Renata de Freitas, Paulo A.S. Veloso, Sheila R.M. Veloso and Petrucio Viana One-and-a-halfth order terms: Curry-Howard and incomplete derivations Murdoch Gabbay and Dominic Mulligan Labelled calculi for Lukasiewicz logics Didier Galmiche and Yakoub Salhi On Characteristic Constants of Theories Defined by Kolmogorov Complexity Shingo Ibuka, Makoto Kikuchi and Hirotaka Kikyo An infinitely-often one-way function based on an average-case assumption Edward Hirsch and Dmitry Itsykson Adversary lower bounds for nonadaptive quantum algorithms Pascal Koiran, Juergen Landes Natacha Portier and Penghui Yao On Second-Order Monadic Groupoidal Quantifiers Juha Kontinen and Heribert Vollmer Using alpha-CTL to specify complex planning goals Silvio Lago Pereira and Leliane Nunes de Barros Hyperintensional Questions Carl Pollard Inference Processes for Quantified Predicate Knowledge Jeff Paris and Soroush Rafiee Rad Skolem theory and Generalized Quantifiers Livio Robaldo ---

1 0

Finite categories and filtered colimits,
by lamarche 23 Apr '08

23 Apr '08

Fellow category theorists, I'm looking for a ref for the following result: Let C be a finite category. Then TFAE -- C has colimits for all small filtered (well, directed is probably better) diagrams. -- Idempotents split in C. This doesn't seem to be in Makkai-Paré or Adamek-Rosicky, but surely somebody must have observed this. Actually the result is a bit more general since idempotents split in *any* category that has filtered colimits. Thanks in advance, François Lamarche

2 1

UTP'08 (revised call for papers)
by Andrew Butterfield 21 Apr '08

21 Apr '08

CALL FOR PAPERS Unifying Theories of Programming 2008 Trinity College, Dublin, Ireland September 8th--10th, 2008 https://www.cs.tcd.ie/utp08/ mailto:utp08@easychair.org ** Proceedings to be published in Springer LNCS ** Important Dates (revised) --------------- Full Paper Submission 8th May, 6am BST Author Notification 23rd June Final Paper 21st July Symposium 8th-10th September Following on the success of the first International Symposium on Unifying Theories of Programming (UTP) held at Walworth Castle in 2006, we are pleased to announce the second, to be held in Dublin in September 2008. Based on the pioneering work on unifying theories of programming of Tony Hoare, He Jifeng, and others, the aims of this Symposium series are to continue to reaffirm the significance of the ongoing UTP project, to encourage efforts to advance it by providing a focus for the sharing of results by those already actively contributing, and to raise awareness of the benefits of such unifying theoretical frameworks among the wider computer science and software engineering communities. Of particular interest is how unification may be used to meet the goals and difficulties to be encountered in the Grand Challenges of Computing, with particular reference to the UK's "GC6: Dependable Systems Evolution", its international cousin the "Verified Software Initiative", and their plan to develop a Verified Software Repository. To this end the Symposium welcomes contributions on the above themes as well as others which can be related to them. Such additional themes include, but are not limited to, relational semantics, relational algebra, healthiness conditions, normal forms, linkage of theories, algebraic descriptions, incorporation of probabilistic programming, timed calculi and object-based descriptions, as well as alternative programming paradigms such as functional, logical, data-flow, and beyond. In all cases, the UTP approach should be compared and advantages/disadvantages discussed. The proceedings will be published in Springer LNCS. Papers may be up to 20 pages (single-column) in length and should ideally be prepared using LaTeX in LNCS format and submitted as pdf files no later than 6am British Summer Time on May 8th, 2008. Paper submission and reviewing will be handled by Easychair ( http://www.easychair.org/conferences/?conf=UTP-08 ) This site is now open for submissions. After the symposium, it is anticipated that selected papers will invited for submission to a journal special issue. Invited Speakers ---------------- Jifeng He, East China Normal University, Shanghai, China Ralph-Johan Back, Abo Akademi University, Finland. Program Committee ----------------- Bernhard Aichernig, Graz University of Technology, Austria Andrew Butterfield (Chair), Trinity College Dublin, Ireland Ana Cavalcanti, University of York, UK Yifeng Chen, University of Durham, UK Steve Dunne, University of Teesside, UK Colin Fidge, Queensland University of Technology, Brisbane, Australia Jeremy Gibbons, University of Oxford, UK Lindsay Groves, Victoria University of Wellington, New Zealand Ian Hayes, University of Queensland, Australia Rick Hehner, University of Toronto, Canada Martin Henson, University of Essex, UK Arthur Hughes, Trinity College Dublin, Ireland Zhiming Liu, United Nations University, Macau David Naumann, Stevens Institute of Technology, New Jersey, US Shengchao Qin, University of Durham, UK Augusto Sampaio, Universidade Federal de Pernambuco, Brazil Jim Woodcock, University of York, UK Huibiao Zhu, East China Normal University, Shanghai, China Local Organisation ------------------ Andrew Butterfield, Arthur Hughes Pawel Gancarski

1 0

EXPRESS'08: preliminary call for papers
by Thomas Hildebrandt 20 Apr '08

20 Apr '08

Apologies for multiple copies.... ----------------------------------------------------------------- 15th International Workshop on Expressiveness in Concurrency (EXPRESS'08) August 23rd, 2008, Toronto (Canada) Affiliated to CONCUR 2008 SCOPE AND TOPICS: The EXPRESS workshops aim at bringing together researchers interested in the relations between various formal systems, particularly in the field of Concurrency. More specifically, they focus on the comparison between programming concepts (such as concurrent, functional, imperative, logic and object-oriented programming) and between mathematical models of computation (such as process algebras, Petri nets, event structures, modal logics, rewrite systems etc.) on the basis of their relative expressive power. SUBMISSION GUIDELINES: Short papers (up to 5 pages, not included in the final proceedings) and Full papers (up to 15 pages) are accepted only in ENTCS-style. Paper submission is performed through the EXPRESS'08 EASYCHAIR server (to be opened on May, 15th). The very best papers will be invited in a special issue of the journal of Mathematical Structures in Computer Science. INVITED SPEAKERs: Michele Bugliesi, Venezia (I), joint with SecCo'08; Gianluigi Zavattaro, Bologna (I). IMPORTANT DATES: Abstract submission: June 1st, 2008 Paper submission: June 8th, 2008. Notification date: July 4th, 2008 Submission of preliminary version for the Proceedings: July 14th, 2008 Submission of final version for ENTCS: September 29th, 2008. WORKSHOP CO-CHAIRS: Daniele Gorla (Dip. di Informatica - Univ. di Roma "La Sapienza", IT) Thomas T. Hildebrandt (IT University of Copenhagen, DK) PROGRAMME COMMITTEE: Julian Bradfield, Edinburgh (UK) Daniele Gorla (co-chair), Rome (I) Thomas Hildebrandt (co-chair), Copenhagen (DK) Gethin Norman, Oxford (UK) Anna Ingólfsdóttir, Reykjavik (IS) Alan Jeffrey, Bell-Labs (USA) Bas Luttik, Eindhoven (NL) Sergio Maffeis, London (UK) Peter Selinger, Dalhousie (CA) Frank Valencia, Paris (F) Daniele Varacca, Paris (F)

1 0

Pregroups seminar, 5 May 2008, Quebec city
by Robert Seely 19 Apr '08

19 Apr '08

A single-day session of talks on the topic of pregroups and grammar has been organized by Daniela Bargelli, as part of the 75th Acfas congress in Quebec city, 5th May 2008. The program may be found on the triples homepage <http://www.math.mcgill.ca/triples/> under "Upcoming meetings", or directly at <http://www.math.mcgill.ca/triples/PreGroupConf-QC08.pdf> For further information, please contact bargelld(a)math.mcgill.ca -= rags =- -- <rags(a)math.mcgill.ca> <www.math.mcgill.ca/rags>

1 0

MFPS 24 Second Call for Participation
by Michael Mislove 17 Apr '08

17 Apr '08

Dear Colleagues, MFPS 14 will take place from May 22 through midday May 25 on the campus of the University of Pennsylvania, Philadelphia. The program for MFPS 24 and the affiliated Tutorial Day on Category Theory and Computer Science, which will take place on May 21, are now online. They can be found at the URL http://www.math.tulane.edu/~mfps/ mfps24.htm There is a link to the registration form for the conference that includes reserving a room at the conference hotel. PLEASE NOTE that the deadline to reserve a hotel room at the conference rate is THIS SUNDAY, APRIL 20. Best regards, Mike Mislove =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA ===============================================

1 0

Equational correspondence and equational embedding
by Philip Wadler 16 Apr '08

16 Apr '08

The notion of *equational correspondence* was defined by Sabry and Felleisen in their paper: Amr Sabry and Matthias Felleisen Reasoning about programs in continuation-passing style LISP and Symbolic Computation, 6(3--4):289--360, November 1993. We lay out below the definition, along with a related notion of *equational embedding*. We've seen relatively little about equational correspondence in the literature, and nothing about equational embedding. Given that these seem to be fundamental concepts, we suspect we've been looking in the wrong places. Any pointers to relevant literature would be greatly apprectiated. An *equational theory* T is a set of terms t of T, and a set of equations t =_T t' (where t, t' are terms of T). Let S, T be equational theories. We say that f : S -> T and g : T -> S constitute an *equational correspondence* between S and T if 1. g(f(s)) =_S s, for all terms s in S 2. f(g(t)) =_T t, for all terms t in T 3. s =_S s' implies f(s) =_T f(s'), for all terms s, s' in S 4. t =_T t' implies g(t) =_S g(t'), for all terms t, t' in T Let S, T be equational theories. We say that f : S -> T and g : f(S) -> S (where f(S) is the image of S under f, a subset of T) constitute an *equational embedding* between S and T if 1. g(f(s)) =_S s, for all s in S 2. s =_S s' implies f(s) =_T f(s'), for all s, s' in S It is easy to see that there is an equational embedding of S into T if and only if there is a function from S to T that preserves and reflects equations. Clearly, f and g constitute an equational correspondence between S and T if f and g constitute an equational embedding of S into T and g and f constitute an equational embedding of T into S. We conjecture that whenever there is an equational embedding of S into T and of T into S that there is an equational correspondence between S and T. This is not immediate, because one equational embedding might be given by f and g and the other by h and k, with no obvious relation between the two. As I said, any pointers to relevant literature would be greatly appreciated! Yours, -- Sam Lindley, Philip Wadler, Jeremy Yallop -- \ Philip Wadler, Professor of Theoretical Computer Science /\ School of Informatics, University of Edinburgh / \ http://homepages.inf.ed.ac.uk/wadler/ The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.

4 3

Research Associate in Semantics of Computation
by Alex Simpson 15 Apr '08

15 Apr '08

Postdoctoral Research Associate in the Semantics of Computation The Laboratory for Foundations of Computer Science at the School of Informatics, University of Edinburgh invites applications for a postdoctoral research associate, tenable for up to three years, on the EPSRC-funded project "Linear Observations and Computational Effects" (EPSRC research grant EP/F042043/1). The project involves the development of category-theoretic models of computation and associated type theories, and the application of these to establishing behavioural properties of programming constructs. The successful applicant will hold a PhD in a relevant area of theoretic computer science or mathematics and will have a good knowledge of category theory and/or type theory and their computer science applications. The post will be taken up as soon as possible. Fixed Term: Up to 3 years Closing date: 30th April 2008 For more information, go to vacancy ref. 3009010 at http://www.jobs.ed.ac.uk/ -- Alex Simpson, LFCS, School of Informatics, Univ. of Edinburgh, UK Email: Alex.Simpson(a)ed.ac.uk Tel: +44 (0)131 650 5113 Web: http://homepages.inf.ed.ac.uk/als Fax: +44 (0)131 667 7209 -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.

1 0

[ICGT'08 Doctoral Symposium] Call for Abstract Submissions
by Andrea Corradini 15 Apr '08

15 Apr '08

================================================================= Call for Abstract Submissions ICGT 2008 Doctoral Symposium http://www.di.unipi.it/~andrea/ICGT08-DS/ An event to be held during ICGT 2008 4th International Conference on Graph Transformation Leicester (United Kingdom), September 9 - 12, 2008 <http://www.cs.le.ac.uk/events/icgt2008> ---------------------------------------------------------------------- The ICGT 2008 Doctoral Symposium will consist of some technical sessions held during the ICGT 2008 Conference, dedicated to presentations by PhD students and by young researchers who completed their doctoral studies within the past two years. ICGT 2008 aims to bring together researchers and practitioners interested in the foundations and applications of graph transformation to a variety of areas. A non-exhaustive list of topics of interest can be found on the conference web pages: <http://www.cs.le.ac.uk/events/icgt2008/Scope.html> Within ICGT 2008, the Doctoral Symposium will provide a unique opportunity for doctoral students and young researchers (having defended their thesis at most two years previously) to interact with established researchers of the graph transformation community and with other students. The Doctoral Symposium will be held on a date to be determined, during the regular activities of the ICGT 2008 conference. Presentations for the Doctoral Symposium will be selected by designated members of the ICGT 2008 Program Committee (see <http://www.cs.le.ac.uk/events/icgt2008/Scope.html> according to originality, significance, and general interest, on the basis of submitted three-pages abstracts. Accepted abstracts, revised according to the comments by the reviewers, will be included in the LNCS proceedings of the Conference. After the conference, selected authors of presentations will be invited to submit a full paper of at most 15 pages for the refereed post-proceedings of the Doctoral Symposium, which is expected to be published as a volume of the Electronic Communications of the EASST (European Association of Software Science and Technology). ---------------------------------------------------------------------- Important Dates May 20, 2008 Submission deadline for abstracts June 2, 2008 Notification of acceptance June 15, 2008 Final abstract due September 10 - 12, 2008 ICGT 2008 Conference in Leicester September 22, 2008 Invitation of full papers (for selected authors only) November 14, 2008 Submission deadline for full papers ---------------------------------------------------------------------- Submissions The abstracts must be up to three pages long including references, and should be formatted preferably using the standard Springer-Verlag LNCS style <http://www.springer.de/comp/lncs/authors.html>. Each abstract can be authored by a single young resarcher (a PhD student, or having defended the thesis in the last two years). The abstracts have to be submitted electronically via the EasyChair system, at the URL <http://www.easychair.org/conferences/?conf=icgt08ds> In the mail accompanying the submission, the author should declare either to be a PhD student, or that he/she defended the thesis not earlier than April 2006. In both cases, please indicate the name of the PhD supervisor. Full papers submitted after the invitation for the post-proceedings can be co-authored by other researchers. ---------------------------------------------------------------------- Grants Discounted fees and grants will be offered for PhD students. Details will published later. ---------------------------------------------------------------------- Organizing committe Andrea Corradini, Pisa (I) Emilio Tuosto, Leicester (UK) ---------------------------------------------------------------------- Contacts For any information about the ICGT 2008 Doctoral Symposium, feel free to contact Andrea Corradini: email: andrea(a)di.unipi.it, phone: +39 050 2212786. ----------------------------------------------------------------------

1 0