A hodgepodge of logic-related papers that have come across my virtual desk these last few weeks.
First though, I should mention the collection of online tutorials and textbooks on logic, both introductory and advanced, that Henri Galinon posted at the Theoreme Logic Toolbox. These include books on model theory, the theory of truth, modal logic, conditional logic, proof theory and substructural logics, many-valued logics, and linguistic applications. (Courtesy of Richard Zach from LogBlog)
Dosen and Petric have a paper out on arXiv on coherence for modalities: "Abstract: Positive modalities in systems in the vicinity of S4 and S5 are investigated in terms of categorial proof theory. Coherence and maximality results are demonstrated, and connections with mixed distributive laws and Frobenius algebras are exhibited."
- Coherence for Modalities, by K. Dosen and Z. Petric
The BEATCS concurrency column, edited by Luca Aceto, presents an article by Dale Miller on operational semantics specifications in logic, showing that "specifications written in SOS, abstract machines, and multiset rewriting, are closely related to Horn clauses, binary clauses, and (a subset of) linear logic, respectively." Plus a host of other interesting things, too.
- Formalizing Operational Semantic Specifications in Logic, by Dale Miller
Beyersdorff et al have a paper out on the complexity of common decision problems for propositional default logic, where they systematically restrict the set of allowed propositional connectives. Probably interesting if you care about default logic in practice.
- The Complexity of Reasoning for Fragments of Default Logic, by O. Beyersdorff, A. Meier, M. Thomas, and H. Vollmer
Dov Gabbay and Karl Schlechta give an overview of logical and semantical rules for nonmonotonic and related logics.
- Roadmap for Preferential Logics, by D. Gabbay and K. Schlechta
I've been quiet here, lately. I was away, visiting Andy Gordon at Microsoft Research, Cambridge for the summer, where we worked on representing stateful computations with types, based on Andy et co.'s RCF language. I will talk about this in the coming months, I believe.
But I'm back in Boston now, and the buzz of the Fall term just starting sounds like a jet engine. I'm teaching two courses, an undergrad Object-Oriented Design course, and a graduate Cryptography and Communication Security course. More on these as the term progresses.
In the latest SIGACT News, there is a nice article about the kind of theory research going on at Google. Not logic per se, but interesting nonetheless. Unsurprisingly, much focus on algorithms and on auctions. Which does remind me of a nice chat I had with a researcher from Google several months ago, after which we concluded that there is a need for a nice specification language for auctions. As far as I can tell, that does not exist. (If you know otherwise, please holler.)
- Theory Research at Google, by G. Aggarwal, N. Ailon, F. Constantin, E. Even-Dar, J. Feldman, G. Frahling, M. Henzinger, S. Muthukrishnan, N. Nisan, M. Pal, M. Sandler, A. Sidiropoulos.