16 citations · 45 across the 11 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.LO2014★ 7 cited
Random strings and tt-degrees of Turing complete C.E. sets
Mingzhong Cai, Rodney G Downey, Rachel Epstein +2
We investigate the truth-table degrees of (co-)c.e.\ sets, in particular, sets of random strings. It is known that the set of random strings with respect to any universal prefix-fr…
math.GT2014
Courcelle's theorem for triangulations
Benjamin A. Burton, Rodney G. Downey
In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for gr…