### Abstract

We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. - Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. - For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.

Original language | English |
---|---|

Title of host publication | Algorithms and Computation |

Subtitle of host publication | 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings |

Editors | Leizhen Cai, Sui-Wing Cheng, Tak-Wah Lam |

Place of Publication | Germany |

Publisher | Springer |

Pages | 372-382 |

Number of pages | 11 |

ISBN (Print) | 978-3-642-45029-7 |

DOIs | |

Publication status | Published - 2013 |

Event | 24th International Symposium, ISAAC 2013 - Hong Kong, China Duration: 16 Dec 2013 → 18 Dec 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 8283 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 24th International Symposium, ISAAC 2013 |
---|---|

Period | 16/12/13 → 18/12/13 |

## Fingerprint Dive into the research topics of 'Myhill-Nerode Methods for Hypergraphs'. Together they form a unique fingerprint.

## Cite this

Van Bevern, R., Fellows, M., Gaspers, S., & Rosamond, F. (2013). Myhill-Nerode Methods for Hypergraphs. In L. Cai, S-W. Cheng, & T-W. Lam (Eds.),

*Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings*(pp. 372-382). (Lecture Notes in Computer Science ; Vol. 8283). Springer. https://doi.org/10.1007/978-3-642-45030-3_35