14 citations · 15 across the 6 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.LO2018
Undecidability of a weak version of MSO+U
Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon +2
We prove the undecidability of MSO on -words extended with the second-order predicate which says that the distance between consecutive positions in a set $X \subseteq \…
cs.FL2018★ 14 cited
Counter Machines and Distributed Automata: A Story about Exchanging Space and Time
Olivier Carton, Bruno Guillon, Fabian Reiter
We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right…