@inproceedings{d8ac065de68f4749a53dd8c71b76d1f9,

title = "Myhill-Nerode Methods for Hypergraphs",

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. ",

keywords = "Cutwidths, Finite tree automaton, Formal language theory, Hyper graph, Incidence graphs, Linear-time, Parameterized complexity, Tree-width, Algorithms, Automata theory, Formal languages, Graph theory",

author = "{Van Bevern}, Rene and Michael Fellows and Serge Gaspers and Frances Rosamond",

year = "2013",

doi = "10.1007/978-3-642-45030-3_35",

language = "English",

isbn = "978-3-642-45029-7",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "372--382",

editor = "Leizhen Cai and Sui-Wing Cheng and Tak-Wah Lam",

booktitle = "Algorithms and Computation",

address = "Switzerland",

note = "24th International Symposium, ISAAC 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

}