47 citations · 159 across the 27 of their papers we have counts for
3 papers · 1 filter
Single use register automata for data words
Mikołaj Bojańczyk, Rafał Stefański
Our starting point are register automata for data words, in the style of Kaminski and Francez. We study the effects of the single-use restriction, which says that a register is emp…
String-to-String Interpretations with Polynomial-Size Output
Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of jus…
MSO+nabla is undecidable
Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
This paper is about an extension of monadic second-order logic over the full binary tree, which has a quantifier saying ``almost surely a branch π \in {0, 1}^w satisfies a formula…