Mikołaj Bojańczyk

Automata with atoms

July 14, 2015
  1. Mikołaj Bojańczyk
    Nominal Monoids. Theory Comput. Syst., 2013   PDF

  2. Mikołaj Bojańczyk, Bartek Klin, Slawomir Lasota
    Automata theory in nominal sets. Logical Methods in Computer Science, 2014   PDF

  3. Mikołaj Bojańczyk, Slawomir Lasota
    A Machine-Independent Characterization of Timed Languages. ICALP (2), 2012   PDF

  4. Mikoł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

Your email address will not be published.