  We give an analog of the Myhill-Nerode methods from formal language theory
for hypergraphs and use it to derive the following results for two NP-hard
hypergraph problems:
  * We provide an algorithm for testing whether a hypergraph has cutwidth at
most k that runs in linear time for constant k. In terms of parameterized
complexity theory, the problem is fixed-parameter linear parameterized by k.
  * We show that it is not expressible in monadic second-order logic whether a
hypergraph has bounded (fractional, generalized) hypertree width. The proof
leads us to conjecture that, in terms of parameterized complexity theory, these
problems are W[1]-hard parameterized by the incidence treewidth (the treewidth
of the incidence graph).
  Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a
method to derive linear-time algorithms and to obtain indicators for
intractability for hypergraph problems parameterized by incidence treewidth.
  In an appendix, we point out an error and a fix to the proof of the
Myhill-Nerode theorem for graphs in Downey and Fellow's book on parameterized
complexity.
