Narrowness, pathwidth, and their application in natural language processing

DOI10.1016/0166-218X(92)90208-RzbMath0767.05058DBLPjournals/dam/KornaiT92WikidataQ58326373 ScholiaQ58326373MaRDI QIDQ1186169

András Kornai, Zsolt Tuza

Publication date: 28 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

natural language processingpathwidthnarrownessdepending grammarshack

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items (12)

Approximating the pathwidth of outerplanar graphs ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ Connections between cutting-pattern sequencing, VLSI design, and flexible machines ⋮ A lower bound for treewidth and its consequences ⋮ The theory of guaranteed search on graphs ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ The complexity of minimum-length path decompositions ⋮ Node-searching problem on block graphs ⋮ Graph searching on chordal graphs ⋮ Complexity of secure sets ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Edge and node searching problems on trees

Cites Work

• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Black-white pebbles and graph separation
• The vertex separation and search number of a graph
• Searching and pebbling
• One-dimensional logic gate assignment and interval graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Narrowness, pathwidth, and their application in natural language processing