# Multiple Context-Free Tree Grammars: Lexicalization and Characterization

@article{Engelfriet2018MultipleCT, title={Multiple Context-Free Tree Grammars: Lexicalization and Characterization}, author={Joost Engelfriet and Andreas Maletti and Sebastian Maneth}, journal={Theor. Comput. Sci.}, year={2018}, volume={728}, pages={29-99} }

Multiple (simple) context-free tree grammars are investigated, where "simple" means "linear and nondeleting". Every multiple context-free tree grammar that is finitely ambiguous can be lexicalized; i.e., it can be transformed into an equivalent one (generating the same tree language) in which each rule of the grammar contains a lexical symbol. Due to this transformation, the rank of the nonterminals increases at most by 1, and the multiplicity (or fan-out) of the grammar increases at most by… Expand

#### Figures and Topics from this paper

#### 5 Citations

Properties of prefix lexicalized synchronous grammars

- Computer Science
- 2018

This work shows that the class of synchronous context-free grammars (SCFG) is not closed under prefix lexicalization, and presents an algorithm for converting a finitely ambiguous, ε-free SCFG to a weakly equivalent prefix lexicalsized synchronous tree-adjoining grammar (STAG). Expand

Lexicalization of Probabilistic Linear Context-free Rewriting Systems

- Computer Science
- IWPT
- 2020

This work aims for a symbiosis between probabilistic linear context-free rewriting systems (PLCFRS) as a Probabilistic grammar formalism and neural models to get the best of both worlds: the interpretability of grammars, and the speed and accuracy of neural models. Expand

Supertagging-based Parsing with Linear Context-free Rewriting Systems

- Computer Science
- NAACL
- 2021

We present the first supertagging-based parser for linear context-free rewriting systems (LCFRS). It utilizes neural classifiers and outperforms previous LCFRS-based parsers in both accuracy and… Expand

Prefix Lexicalization of Synchronous CFGs using Synchronous TAG

- Computer Science
- ACL
- 2018

This work shows that an epsilon-free, chain-free synchronous context-free grammar (SCFG) can be converted into a weakly equivalent synchronous tree-adjoining grammar (STAG) which is prefix lexicalized, and proves new formal properties about SCFG. Expand

Syntactical analysis of context-free languages taking into account order of application of productions

- Computer Science
- Journal of Physics: Conference Series
- 2019

#### References

SHOWING 1-10 OF 116 REFERENCES

Multiple Context-Free Grammars

- 2007

Multiple context-free grammar (MCFG) is a weakly contextsensitive grammar formalism that deals with tuples of strings. An MCFG is called m-MCFG if all tuples have at most m components. In this… Expand

Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars

- Computer Science
- FCT
- 2017

It is demonstrated that multiple simple context-free tree Grammars are as expressive as multi-component tree adjoining grammars and that both allow strong lexicalization. Expand

Parameter reduction and automata evaluation for grammar-compressed trees

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2012

It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. Expand

On the Generative Power of Multiple Context-Free Grammars and Macro Grammars

- Computer Science
- IEICE Trans. Inf. Syst.
- 2008

The generative power of several subclasses of variable-linear macro Grammars and that of multiple context-free grammars are compared in details. Expand

The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars

- Mathematics, Computer Science
- J. Log. Lang. Inf.
- 2011

A proof of the strong equivalence of these grammar formalisms is presented showing that a tree language is a member of this class iff it is the two-dimensional yield of an MSO-definable three-dimensional tree language. Expand

Spinal-Formed Context-Free Tree Grammars

- Mathematics, Computer Science
- Theory of Computing Systems
- 2000

It is shown that the class of string languages generated by spine Grammars coincides with that of tree adjoining grammars. Expand

Parsing Strategies with ‘Lexicalized’ Grammars: Application to Tree Adjoining Grammars

- Computer Science
- COLING
- 1988

A novel general parsing strategy for 'lexicalized' grammars is discussed and it is argued that even if one extends the domain of locality of CFGs to trees, using only substitution does not give the freedom to choose the head of each structure. Expand

Strong Lexicalization of Tree Adjoining Grammars

- Computer Science
- ACL
- 2012

Simple context-free tree grammar strongly lexicalize tree adjoining grammars and themselves, in which each production contains a lexical symbol. Expand

Context-free grammars: Covers, normal forms, and parsing

- Computer Science
- Lecture Notes in Computer Science
- 1980

This monograph develops a theory of grammatical covers, normal forms and parsing by introducing algorithms that describe a transformation of an input grammar into an output grammar which satisfies the requirements. Expand

Tree-adjoining grammars and lexicalized grammars

- Computer Science
- Tree Automata and Languages
- 1992

A tree generating system called tree-adjoining grammar(TAG) is described and some of the recent results about TAGs are state, which would be of interest to researchers in tree grammars and tree automata. Expand