Matroids Hitting Sets and Unsupervised Dependency Grammar Induction
classification
💻 cs.DM
cs.CLcs.DS
keywords
graphcomputationalgrammarinductionproblemalgorithmalgorithmsapproximation
pith:AIJ3UGAE Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{AIJ3UGAE}
Prints a linked pith:AIJ3UGAE badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
This paper formulates a novel problem on graphs: find the minimal subset of edges in a fully connected graph, such that the resulting graph contains all spanning trees for a set of specifed sub-graphs. This formulation is motivated by an un-supervised grammar induction problem from computational linguistics. We present a reduction to some known problems and algorithms from graph theory, provide computational complexity results, and describe an approximation algorithm.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.