Duality For Logic On Words

An EU-funded initiative has made strides in combining work and collaborations on two previously separate mathematical theories to address important challenges in complexity theory. This research was undertaken with the support of the Marie Curie programme.

The general aim of this research field is to understand how ‘difficult’ it is to find an algorithmic solution to a computational problem. However, to answer this question, a decision must first be made on what a good measure for ‘difficulty’ is. For example, is it related to the time needed for an average personal computer to solve the problem or the amount of memory space required? Or, is it a combination of the two? This general method of describing the difficulty of a problem through logic is called descriptive complexity.

“In the project DFLOW, we studied a number of specific logical systems, known as logics on finite and infinite words,” explains project research fellow Dr Sam van Gool. The term ‘words’, he points out, refers to data with a one-dimensional, linear structure, which can be read from left to right, as opposed to tree-structured data, for example.

He explains that while the study of these logical systems is not a new area, “the main novelty of DFLOW was to combine two different and previously separate mathematical theories in attacking the main challenges in this research field.” The aim of DFLOW was to apply this recent idea of combining these theories – semigroup theory and Stone duality – to a specific class of logical systems.

Expert collaborations

Having previously studied the mathematical theory of Stone duality, Dr van Gool wanted to use this project to expand his knowledge of semigroup theory and its use for studying logics. This was realised through research collaborations with Prof. Benjamin Steinberg and Prof. Yde Venema, at City College of New York and the University of Amsterdam, respectively.

The project also helped to catalyse other relevant research collaborations. Specifically, the fellow reports, “the project helped make progress on joint work with Prof. Silvio Ghilardi (University of Milan) on logical systems and another mathematical topic called model theory.”

It follows then that the main output of the 3-year project comprises 9 research articles by Dr van Gool. Four of these were co-authored with Prof. Steinberg. One more research article in collaboration with Prof. Venema and another two with Prof. Steinberg are still in preparation.

Given the project’s cross-over nature, special care was taken to disseminate the research in both mathematics and computer science contexts. The project fellow notes the most prestigious publication on the mathematical side is that co-authored with Prof. Steinberg and published in Advances in Mathematics. On the computer science side, he gives this place to the Symposium on Logic in Computer Science (LICS 2016) publication with Prof. Ghilardi.

Bringing the two fields together

When asked about the project’s biggest success, Dr van Gool emphasised “the creation of a new collaboration between experts in the fields of semigroup theory and Stone duality in logic.” This is an important step as there was previously limited interaction between the two.

Dr van Gool will build on project achievements. He plans to extend some methods to more complex data structures, including trees. Another planned research direction involves very recent developments in logical systems related to those considered in DFLOW.

Reference source: Duality For Logic On Words