Mikołaj Bojańczyk

July 14, 2015

Mikołaj Bojańczyk

*Nominal Monoids.*Theory Comput. Syst., 2013 PDFMikołaj Bojańczyk, Bartek Klin, Slawomir Lasota

*Automata theory in nominal sets.*Logical Methods in Computer Science, 2014 PDFMikołaj Bojańczyk, Slawomir Lasota

*A Machine-Independent Characterization of Timed Languages.*ICALP (2), 2012 PDFMikołaj Bojańczyk, Luc Segoufin, Szymon Torunczyk

*Verification of database-driven systems via amalgamation.*PODS, 2013 PDF

This is a series of papers on the question: “what is a regular language in sets with atoms?” and as such is a part of the project on sets with atoms. The first paper is about orbit-finite monoids, and it proves a Schützenberger theorem for them, demonstrating that the structural theory of monoids extends rather smoothly to orbit-finite monoids. Paper [2] studies orbit-finite automata, which are more powerful than finite monoids. In a certain sense, orbit-fintie automata are the same thing as register automata of Francez and Kaminski, but the formalism of orbit-finiteness is a bit more flexible, e.g. allowing a Myhill-Nerode theorem and effective minimization. Paper [3] continues the study of the Myhill-Nerode theorem, but it does so for a kind of atoms that correspond to timed automata, where the assumptions of paper [2] are not satisfied. Finally, paper [4] gives a database angle on the automata from [2], although it tries to avoid using the word *atom *in order not to annoy database theorists, including Luc Segoufin.

Paper [1] is a journal version of

Mikołaj Bojańczyk

*Data Monoids.*STACS, 2011 PDF

In the STACS paper above, the terminology is a bit antiquated, because at the time I was not aware of the existence of nominal sets or atoms. Paper [2] is a journal version

Mikołaj Bojańczyk, Bartek Klin, Slawomir Lasota

*Automata with Group Actions.*LICS, 2011 PDF

which is already aware of nominal sets. I think that maybe an easier to follow description of the topic of [2] is the book that I am writing (with very little recent progress). The initial chapters, which cover automata, should be in a relatively good state.

## Leave a Reply