2 papers
cs.DM2026
Graph subshifts
Pablo Arrighi, Amélia Durbec, Pierre Guillon
We propose a definition of graph subshifts of finite type that can be seen as extending both the notions of subshifts of finite type from classical symbolic dynamics and finitely p…
cs.CC2026
Hardness of monadic second-order formulae over succinct graphs
Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon +3
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graph…