5 citations · 10 across the 8 of their papers we have counts for
9 papers · 1 filter
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…
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…
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.
Star Height via Games
Mikolaj Bojanczyk
This paper proposes a new algorithm deciding the star height problem. As shown by Kirsten, the star height problem reduces to a problem concerning automata with counters, called li…
It is undecidable if two regular tree languages can be separated by a deterministic tree-walking automaton
Mikołaj Bojańczyk
The following problem is shown undecidable: given regular languages L,K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L…
Definability equals recognizability for graphs of bounded treewidth
Mikołaj Bojańczyk, Michał Pilipczuk
We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is re…