How to enumerate trees from a context-free grammar
I present a simple algorithm for enumerating the trees generated by a Context Free Grammar (CFG). The algorithm uses a pairing function to form a bijection between CFG derivations and natural numbers, so that trees can be uniquely decoded from counting. This provides a general way to number expressions in natural logical languages, and potentially can be extended to other combinatorial problems. I also show how this algorithm may be generalized to more general forms of derivation, including analogs of Lempel-Ziv coding on trees.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Compound Probabilistic Context-Free Grammars for Grammar Induction
We study a formalization of the grammar induction problem that models sentences as being generated by a compound probabilistic context-free grammar. In contrast to traditional formulations which learn a single stochastic…
Constituency Grammar InductionSentenceVariational InferenceA Wide-Coverage Context-Free Grammar for Icelandic and an Accompanying Parsing System
We present an open-source, wide-coverage context-free grammar (CFG) for Icelandic, and an accompanying parsing system. The grammar has over 5,600 nonterminals, 4,600 terminals and 19,000 productions in fully expanded for…
ArticlesJoint learning of ontology and semantic parser from text
Semantic parsing methods are used for capturing and representing semantic meaning of text. Meaning representation capturing all the concepts in the text may not always be available or may not be sufficiently complete. On…
Semantic ParsingLexicalization of Probabilistic Linear Context-free Rewriting Systems
In the field of constituent parsing, probabilistic grammar formalisms have been studied to model the syntactic structure of natural language. More recently, approaches utilizing neural models gained lots of traction in t…
Vector symbolic architectures for context-free grammars
Background / introduction. Vector symbolic architectures (VSA) are a viable approach for the hyperdimensional representation of symbolic data, such as documents, syntactic structures, or semantic frames. Methods. We pres…
Explainable artificial intelligenceExplainable Artificial Intelligence (XAI)