Undecidability of the bandwidth problem on linear graph languages

DOI10.1016/0020-0190(89)90140-3zbMath0693.68045OpenAlexW2059171004MaRDI QIDQ908714

Manfred Wiegers, Egon Wanke

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90140-3

zbMATH Keywords

undecidabilitybandwidthmonadic second-order logicgraph grammargraph languagesPost's correspondence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Languages that Capture Complexity Classes
• Graph expressions and graph rewritings
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time