Aggregative combinatorics: An introduction

Tara Nicholson
Martin Allen

Abstract

This paper is an exploratory introduction to issues surrounding the combinatorial expressivity and computational complexity of weakly aggregative modal logic (WAL) -- the latter insofar as it relates to the former, but also more generally. We begin by showing how WAL allows us to define a natural hierarchy of (recognition) optimization problems not generally available in logics as strong as K. In this respect we illustrate that an important advantage of the Aggregative Programme in modal logic (as dubbed by its progenitors, Jennings and Schotch) over the standard modal paradigm, which views K as the weakest normal modal logic, has to do with its expressive, discriminatory power. As an extended example in this context we formulate the Four Colour Theorem (Every planar graph is 4-colourable) (4CT) as a rule schema in WAL which preserves validity with respect to quinary relational frames if and only if 4CT is true. Accordingly, because WAL is decidable, additional motivations for exploring its combinatorial expressivity arise from issues of decidability in graph theory. In closing we analyze the complexity of the satisfiability problem for these logics. 

@InProceedings{Nicholson03,
  author = 	 {Tara Nicholson and Martin Allen},
  title = 	 {Aggregative Combinatorics: An Introduction},
  booktitle =    {Proceedings of the Student Session, 
                  Second North American Summer School in Logic, Language, and Information ({NASSLLI}-03)},
  pages = 	 {15-25},
  year = 	 2003,
  address =      {Bloomington, IN}
}

Download [pdf]