5 citations · 10 across the 8 of their papers we have counts for
16 papers
Separator logic and star-free expressions for graphs
Mikolaj Bojanczyk
We describe two formalisms for defining graph languages, and prove that they are equivalent: 1. Separator logic. This is first-order logic on graphs which is allowed to use the edg…
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…
Polyregular Functions
Mikołaj Bojańczyk
This paper is about certain string-to-string functions, called the polyregular functions. These are like the regular string-to-string functions, except that they can have polynomia…
Two monads for graphs
Mikolaj Bojanczyk
An introduction to algebras for graphs, based on Courcelle's algebras of hyperedge replacement and vertex replacement. The paper uses monad notation.