- \n
- An ICALP paper by\u00a0 Arnborg, Lagergren and Seese called\u00a0Problems easy for tree-decomposable graphs<\/a><\/em> (1988).<\/a> The\u00a0journal version appeared in 1991.<\/li>\n
- The journal version of Courcelle’s\u00a0The monadic second-order logic of graphs V<\/a> (1991). <\/em>The technical report appeared in 1989.<\/li>\n
- A workshop paper by Engelfriet called \u00a0A characterization of context-free NCE graph languages by monadic second-order logic on trees<\/a><\/em> (1991)<\/a>\u00a0The paper cites slides of Engelfriet from 1988.<\/li>\n<\/ul>\n
If, for reasons of brevity, one wishes to cite just a single paper, while still using a source close to the originals, then one can use:<\/p>\n
- \n
- \u00a0the survey\u00a0Monadic second-order definable graph transductions: a survey<\/a> (1994) <\/em>by Courcelle<\/li>\n
- the book\u00a0Graph Structure and Monadic Second-Order Logic – A Language-Theoretic Approach (2012)<\/a>\u00a0<\/em>by Courcelle and Engelfriet<\/li>\n<\/ul>\n
A longer discussion is given below. \u00a0In his survey article from 1994, Courcelle tells the following story:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-21.34.35-1-1024x137.png\")
<\/p>\n
Paper [1] is the Arnborg et al. paper from 1988. Paper [22] is the 1991 paper of \u00a0Engelfriet from 1991. Papers [9,10,13] are items VI, V, VII of Courcelle’s series The monadic second-order logic of graphs<\/em>, published in 1990 and 1991. Finally [15] is a joint research report of Courcelle and Engelfriet.<\/p>\n
Papers [1,22,9] are discussed below.<\/p>\n
We begin with Arnborg et al., which has the earliest date.\u00a0In Problems easy for tree-decomposable graphs (1988), <\/em>by\u00a0 Arnborg, Lagergren and Seese, the authors introduce a version of \u00a0mso transductions and place it in context as follows:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-22.05.25-1024x85.png\")
<\/p>\nHere is their definition:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-22.04.13-1024x321.png\")
<\/p>\n
It is worth pointing out that this definition is a function, i.e. it does not have nondeterministic colouring. Also, it allows quotienting, thanks to \u03b5, which is a feature commonly used for first-order interpretations, but which has not caught on for mso transductions. Maybe it has not caught on since the existentially guessed colouring, which will appear in Courcelle’s definition, eliminates the need for quotienting.<\/p>\n
We now move on to the Engelfriet paper,\u00a0A characterization of context-free NCE graph languages by monadic second-order logic on trees (1991)<\/em>. \u00a0Englefriet gives the following story of mso transductions, which is the same as Courcelle’s:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-22.06.53-1024x132.png\")
<\/p>\nEnelfriet’s definition is this:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-22.06.15-1024x510.png\")
<\/p>\nAlso here, there is no nondeterministic colouring. The definition is for the vocabulary of graphs, but of course any reasonable person can apply it to other structures. The above definition does not allow quotienting, but it does allow defining partial functions, thanks to the domain formula.<\/p>\n
Finally, let’s look at Courcelle’s\u00a0The monadic second-order logic of graphs V <\/em>from 1991. Here we find the following definition of mso transductions:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-22.32.32-1024x767.png\")
<\/p>\nThe eagle-eyed reader will notice two features that were not present in the previous definitions: copying (this is the number k<\/em>) and an existentially quantified colouring of the input structure (this is W<\/em>). Copying is maybe not such a big deal, but the colouring is important. For example, in the same paper Courcelle states his conjecture:<\/p>\n
![\"\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/upload\/Screenshot-2019-12-07-at-22.38.30-1024x93.png\")
<\/p>\n - the book\u00a0Graph Structure and Monadic Second-Order Logic – A Language-Theoretic Approach (2012)<\/a>\u00a0<\/em>by Courcelle and Engelfriet<\/li>\n<\/ul>\n
- The journal version of Courcelle’s\u00a0The monadic second-order logic of graphs V<\/a> (1991). <\/em>The technical report appeared in 1989.<\/li>\n