Undecidability of the bandwidth problem on linear graph languages

DOI10.1016/0020-0190(89)90140-3MaRDI QIDQ908714zbMATH OpenOpenAlexFDO

Authors 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

bandwidthmonadic second-order logicundecidabilitygraph languagesgraph grammarPost's correspondence problem

Mathematics Subject Classification ID

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

Recommendations

• Decision problems for edge grammars
• Bounding the bandwidths for graphs
• Bandwidth of Bipartite Permutation Graphs
• scientific article; zbMATH DE number 4070955
• scientific article; zbMATH DE number 719423

Cites work

• scientific article; zbMATH DE number 4049098 (Why is no real title available?)
• scientific article; zbMATH DE number 4049099 (Why is no real title available?)
• scientific article; zbMATH DE number 4081531 (Why is no real title available?)
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Graph expressions and graph rewritings
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Languages that Capture Complexity Classes

This page was built for publication: Undecidability of the bandwidth problem on linear graph languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908714)