Fact. For every classical papers in a given field, there will be mustard watch papers.
Slajdomat is a tool that I am developing for making zooming slides in Figma. You can find the tool at GitHub, including source code, binaries and documentation. This is a good place for sending bug reports and feature requests. If you might want to joint the project, let me know, although I admit I have no experience in managing a software project.
I logged into my easychair account, and downloaded the average referee scores for 184 accepted papers. These are taken from conferences (ICALP, STACS and LICS) where I was in the PC, so I had access to the scores for the papers. In all cases, the scores were on a scale of -3 to +3, so they can be compared. Next, for each paper I looked at the number citations, according to google scholar. Here is the result (y axis is citations and x axis is average referee score):
You will see that there does not seem to be any strong relationship between the two variables. In fact, the correlation is negative (-0.004539).
I understand that citation counts are a questionable metric, whose main advantage is that it can be counted and drawn in a scatter plot. Nevertheless, I think that these results are evidence for the fact that reviews, especially for conferences, do not reflect the value of the paper. My personal impression is that for conferences, higher scores are given for papers of the kind “we continue the work of x by solving problem y” and lower scores are given for papers of the kind “we introduce a new idea”. On the other hand, the impact (and therefore also citations) is greater for the second kind.
Of course I do not recommend to get rid of reviews, since there does not seem to be any better system.
The trick. You cannot write “as shown in [3]”, but you need to write “as shown in [3, Theorem 2]” or “as shown in [3, p. 122]”.
Analysis. This does not take too much work. When first citing a result/definition, you need to invest 5 minutes to download the paper and then search for “Theorem” or “Main Theorem”. Advantages of this system:
This page is intended as notes, mainly for myself, about the history of some notions in logic and automata. But maybe they can be useful to others. These notes will surely have many wrong statements, so I welcome comments and corrections.
An mso transduction is a transformation which inputs a structure (a word, tree, graph, etc.) and outputs another structure. My conclusion is that mso transductions can be credited to the following papers:
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:
A longer discussion is given below. In his survey article from 1994, Courcelle tells the following story:
Paper [1] is the Arnborg et al. paper from 1988. Paper [22] is the 1991 paper of Engelfriet from 1991. Papers [9,10,13] are items VI, V, VII of Courcelle’s series The monadic second-order logic of graphs, published in 1990 and 1991. Finally [15] is a joint research report of Courcelle and Engelfriet.
Papers [1,22,9] are discussed below.
We begin with Arnborg et al., which has the earliest date. In Problems easy for tree-decomposable graphs (1988), by Arnborg, Lagergren and Seese, the authors introduce a version of mso transductions and place it in context as follows:
Here is their definition:
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 ε, 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.
We now move on to the Engelfriet paper, A characterization of context-free NCE graph languages by monadic second-order logic on trees (1991). Englefriet gives the following story of mso transductions, which is the same as Courcelle’s:
Enelfriet’s definition is this:
Also 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.
Finally, let’s look at Courcelle’s The monadic second-order logic of graphs V from 1991. Here we find the following definition of mso transductions:
The eagle-eyed reader will notice two features that were not present in the previous definitions: copying (this is the number k) and an existentially quantified colouring of the input structure (this is W). Copying is maybe not such a big deal, but the colouring is important. For example, in the same paper Courcelle states his conjecture:
The solution of this conjecture crucially relies on the colouring. For linearly ordered input structures, such as trees or words, the colouring is less important, since the lexicographically least colouring that works can be computed by a formula.
You can get points by either finding mistakes in the atom book or by solving problems.
Grades:3=2 points, 4=2.5 points, 5=3 points.
Deadline: June 30
Each mistake in the atom book (not counting solutions to exercises) gets you 0.1 points. Mark the mistakes on this page with your name, if it does not work you can use this google docs. Mistakes also include typos, bad grammar, and unclear parts (explain why), generally speaking anything that requires improvement. You don’t need to start to read the book from the beginning. The lecture corresponds to Chapters 3,4,7 and 10, but you are encouraged to find mistakes in other parts (later chapters have a higher expected mistake rate, so it might be profitable to look at them).
Each of the problems (see below) gets you 1 point if it is solved by ≥3 people including you, 2 points otherwise.
for some Find an example of oligomorphic atoms and a language over input alphabet which is recognised by a deterministic orbit-finite automaton, but is not recognised by any equivariant deterministic register automaton.
(b) there is some such that property can be defined by a formula of first-order logic which has shape
Define the regular expressions to be the smallest class of languages (over orbit-finite alphabets) which: contains all languages with finitely many words and is closed under orbit-finite union, concatenation and Kleene star . Do regular expressions define the same languages as nondeterministic-orbit finite automata?
The Lipa Summer School (click here for the page of the school, including registration) is a summer school on topics connected to logic in computer science. The school consists of 4 mini-courses given by:
My slides are now deemed a security risk. To run them in Chrome, click this button:
I promise I’m not trying to hurt your computer. Promise.
I will be working on a better solution.
These slides show how to decide equivalence of tree-to-string transducers using the Hilbert Basis Theorem. The idea is based on
Helmut Seidl, Sebastian Maneth, Gregor Kemper:
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. FOCS 2015: 943-962
There are two parts:
The Lipa Summer School (click here for the page of the school, including registration) is a summer school on topics connected to logic in computer science. There will be 4 mini-courses given by:
I am leading an ERC Consolidator grant on automata and logic called “A unified theory of finite-state recognisability”. The main goal is to find algebraic structures (like monoids) for things like infinite trees or profinite words. However, I can be very flexible on the topic, as long as it is tangentially connected to logic or automata.
I am searching for talented postdocs and phd students. The deadline for applications is April 30, 2017. Send applications to me by email. Please feel to ask questions before that date!
Postdocs. The postdoc can begin at any time from June 1 until the end of 2017. The duration is 6 – 12 months, with a possibility of extension for another year. The application consists of your name and 1-2 names of people who can provide references. I am looking for people with a good track record in the top conferences of the field. Teaching is optional.
PhD students. A typical duration is 4 years, starting any time from June 1 until the end of 2017. In application please include a cv and 1-2 names of people who can provide references. I am looking for candidates with a strong background in mathematics.
Here is a way of drawing graphs of bounded tree width, inspired by metro maps. The horizontal black lines are graph edges, the coloured shapes are vertices, and the gray background is the tree underlying the decomposition.
The mathematical content of the picture is that a graph has tree width k if and only if it is a subgraph of a (k+1)-colourable chordal graph (thanks to Michał Pilipczuk for pointing this out).
In 2013, I joined the EATCS council. Here is what I promised to do:
I am a candidate for the EATCS council. My program consists of three items. The first item is something where I promise concrete action, the remaining two are more speculative.
Update. The first item is solved: starting with 2016, ICALP will be using the open access LIPICS system. As it turned out, this idea had overwhelming support inside the council.
A presentation on documents about Mojżesz Presburger from the archives of Warsaw University
The documents in high resolution:
Birth certificate (Presburger was born in 1904, but this document is from August 1923)
Application to study at Warsaw University (September 1923)
Hand-written CV (September 1923)
Courses for the winter semester in 1924
Courses for the autumn/winter trimester in 1927/28
Graduation diploma (October 1930) (1/2)
Graduation diploma (October 1930) (2/2)
Court document concerning 70 złoty unpaid tuition (January 1939)