TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 22.11.2012


Page Content

to Navigation

How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding

Dipl.-Inf. René van Bervern (TU Berlin)

A trellis is a graph associated with a linear code that is used for maximum-likelihood decoding. The decoding complexity of a linear code is strongly influenced by the state complexity of the trellis, which highly depends on the coordinate permutation of the linear code. The problem of finding the coordinate permutation of a linear code such that the state-complexity of the associated trellis is at most k has been referred to as the Art of Trellis Decoding and is NP-hard. We how that it is linear-time solvable if k is constant. To this end, we reduce the problem to Hypergraph Cutwidth, which we show to be fixed-parameter linear by, for the first time, applying an analog of the Myhill-Nerode theorem from formal language theory to a hypergraph problem.

22.11.2012 16:00
René van Bevern
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe