output
20062021
most citedModel-checking ATL under Imperfect Information and Perfect Recall Semantics is Undecidable

77 citations

researchers with a paper here
collaborating institutions
Showing 2018 · cs.CCShow all

2 papers · 2 filters

cs.CC2018★ 2 cited

Unifying lower bounds for algebraic machines, semantically

Thomas Seiller, Luc Pellissier, Ulysse Léchine

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it…

cs.CC2018

Undecidable word problem in subshift automorphism groups

Pierre Guillon, Emmanuel Jeandel, Jarkko Kari +1

This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose aut…