5 citations · 10 across the 9 of their papers we have counts for
4 papers · 1 filter
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…
Emptiness of zero automata is decidable
Mikolaj Bojańczyk, Hugo Gimbert, Edon Kelmendi
Zero automata are a probabilistic extension of parity automata on infinite trees. The satisfiability of a certain probabilistic variant of mso, called tmso + zero, reduces to the e…
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…
Some connections between universal algebra and logics for trees
Mikołaj Bojańczyk, Henryk Michalewski
One of the major open problems in automata and logic is the following: is there an algorithm which inputs a regular tree language and decides if the language can be defined in firs…