On the Parameterized Complexity of Linear Context-Free Rewriting Systems
Martin Berglund, Henrik Björklund, Frank Drewes · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2013
We study the complexity of uniform membership for Linear Context-Free RewritingSystems, i.e., the problem where we aregiven a string w and a grammar G and areasked whether w ∈ L(G). In particular,we use parameterized complexity theoryto investigate how the complexity dependson various parameters. While we focusprimarily on rank and fan-out, derivationlength is also considered.