An Exploration of Left-Corner Transformations
- URL: http://arxiv.org/abs/2311.16258v1
- Date: Mon, 27 Nov 2023 19:04:37 GMT
- Title: An Exploration of Left-Corner Transformations
- Authors: Andreas Opedal, Eleftheria Tsipidi, Tiago Pimentel, Ryan Cotterell,
Tim Vieira
- Abstract summary: This paper generalizes prior left-corner transformations to support semiring-weighted production rules.
We provide several technical results regarding the formal relationships between the outputs of GLCT, speculation, and the original grammar.
- Score: 71.29080123997137
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to
remove left recursion from context-free grammars, which is an important step
towards making the grammar parsable top-down with simple techniques. This paper
generalizes prior left-corner transformations to support semiring-weighted
production rules and to provide finer-grained control over which left corners
may be moved. Our generalized left-corner transformation (GLCT) arose from
unifying the left-corner transformation and speculation transformation (Eisner
and Blatz, 2007), originally for logic programming. Our new transformation and
speculation define equivalent weighted languages. Yet, their derivation trees
are structurally different in an important way: GLCT replaces left recursion
with right recursion, and speculation does not. We also provide several
technical results regarding the formal relationships between the outputs of
GLCT, speculation, and the original grammar. Lastly, we empirically investigate
the efficiency of GLCT for left-recursion elimination from grammars of nine
languages.
Related papers
- On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
Chain-of-thought (CoT) reasoning has improved the performance of modern language models (LMs)
We show that LMs can represent the same family of distributions over strings as probabilistic Turing machines.
arXiv Detail & Related papers (2024-06-20T10:59:02Z) - Controlled Generation with Prompt Insertion for Natural Language
Explanations in Grammatical Error Correction [50.66922361766939]
It is crucial to ensure the user's comprehension of a reason for correction.
Existing studies present tokens, examples, and hints as to the basis for correction but do not directly explain the reasons for corrections.
Generating explanations for GEC corrections involves aligning input and output tokens, identifying correction points, and presenting corresponding explanations consistently.
This study introduces a method called controlled generation with Prompt Insertion (PI) so that LLMs can explain the reasons for corrections in natural language.
arXiv Detail & Related papers (2023-09-20T16:14:10Z) - Compositional Generalization without Trees using Multiset Tagging and
Latent Permutations [121.37328648951993]
We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens.
Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations.
Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
arXiv Detail & Related papers (2023-05-26T14:09:35Z) - On Parsing as Tagging [66.31276017088477]
We show how to reduce tetratagging, a state-of-the-art constituency tagger, to shift--reduce parsing.
We empirically evaluate our taxonomy of tagging pipelines with different choices of linearizers, learners, and decoders.
arXiv Detail & Related papers (2022-11-14T13:37:07Z) - Translate First Reorder Later: Leveraging Monotonicity in Semantic
Parsing [4.396860522241306]
TPol is a two-step approach that translates input sentences monotonically and then reorders them to obtain the correct output.
We test our approach on two popular semantic parsing datasets.
arXiv Detail & Related papers (2022-10-10T17:50:42Z) - Learning Bounded Context-Free-Grammar via LSTM and the
Transformer:Difference and Explanations [51.77000472945441]
Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks.
In practice, it is often observed that Transformer models have better representation power than LSTM.
We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns.
arXiv Detail & Related papers (2021-12-16T19:56:44Z) - A Unifying Theory of Transition-based and Sequence Labeling Parsing [14.653008985229617]
We map transition-based parsing algorithms that read sentences from left to right to sequence labeling encodings of syntactic trees.
This establishes a theoretical relation between transition-based parsing and sequence-labeling parsing.
We implement sequence labeling versions of four algorithms, showing that they are learnable and obtain comparable performance to existing encodings.
arXiv Detail & Related papers (2020-11-01T18:25:15Z) - On embedding Lambek calculus into commutative categorial grammars [0.0]
We consider tensor grammars, which are an example of commutative" grammars, based on the classical (rather than intuitionistic) linear logic.
The basic ingredient are tensor terms, which can be seen as encoding and generalizing proof-nets.
arXiv Detail & Related papers (2020-05-20T14:08:56Z) - Traduction des Grammaires Cat\'egorielles de Lambek dans les Grammaires
Cat\'egorielles Abstraites [0.0]
This internship report is to demonstrate that every Lambek Grammar can be, not entirely but efficiently, expressed in Abstract Categorial Grammars (ACG)
The main idea is to transform the type rewriting system of LGs into that of Context-Free Grammars (CFG) by erasing introduction and elimination rules and generating enough axioms so that the cut rule suffices.
Although the underlying algorithm was not fully implemented, this proof provides another argument in favour of the relevance of ACGs in Natural Language Processing.
arXiv Detail & Related papers (2020-01-23T18:23:03Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.