4 papers
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
Colin Geniet, Aliénor Goubault-Larrecq, Kévin Perrot
We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed…
Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
Aliénor Goubault-Larrecq, Kévin Perrot
A new proof technique combining finite model theory and dynamical systems has recently been introduced to obtain general complexity lower bounds on any question one may formulate o…
Rice-like complexity lower bounds for Boolean and uniform automata networks
Aliénor Goubault-Larrecq, Kévin Perrot
Automata networks are a versatile model of finite discrete dynamical systems composed of interacting entities (the automata), able to embed any directed graph as a dynamics on its…
New Algorithms for Combinations of Objectives using Separating Automata
Ashwani Anand, Nathanaël Fijalkow, Aliénor Goubault-Larrecq +2
The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that…