research
∙
07/06/2023
Efficient Semiring-Weighted Earley Parsing
This paper provides a reference description, in the form of a deduction ...
share
research
∙
06/29/2023
A Formal Perspective on Byte-Pair Encoding
Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data...
research
∙
01/17/2023
Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
Weighted finite-state automata (WSFAs) are commonly used in NLP. Failure...
research
∙
10/13/2022
Algorithms for Weighted Pushdown Automata
Weighted pushdown automata (WPDAs) are at the core of many natural langu...
research
∙
09/14/2022
On the Intersection of Context-Free and Regular Languages
The Bar-Hillel construction is a classic result in formal language theor...
research
∙
05/03/2022
Exact Paired-Permutation Testing for Structured Test Statistics
Significance testing – especially the paired-permutation test – has play...
research
∙
09/14/2021
Searching for More Efficient Dynamic Programs
Computational models of human language often involve combinatorial probl...
research
∙
09/14/2021
Efficient Sampling of Dependency Structures
Probabilistic distributions over spanning trees in directed graphs are a...
research
∙
06/01/2021
On Finding the K-best Non-projective Dependency Trees
The connection between the maximum spanning tree in a directed graph and...
research
∙
06/01/2021
Higher-order Derivatives of Weighted Finite-state Machines
Weighted finite-state machines are a fundamental building block of NLP s...
research
∙
10/20/2020
Evaluation of Logic Programs with Built-Ins and Aggregation: A Calculus for Bag Relations
We present a scheme for translating logic programs, which may use aggreg...
research
∙
10/06/2020
If beam search is the answer, what was the question?
Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural ...
research
∙
10/06/2020
Please Mind the Root: Decoding Arborescences for Dependency Parsing
The connection between dependency trees and spanning trees is exploited ...
research
∙
08/29/2020
Efficient Computation of Expectations under Spanning Tree Distributions
We give a general framework for inference in spanning tree models. We pr...
research
∙
07/08/2020
Best-First Beam Search
Decoding for many NLP tasks requires a heuristic algorithm for approxima...
research
∙
09/30/2019