Mark-Jan Nederhof
Biographic Data
| ID | 6536242 |
|---|---|
| NAME | Mark-Jan Nederhof |
| GIVEN NAMES | Mark-Jan |
| FAMILY NAME | Nederhof |
| SIGNATURE | NEDERHOF M |
| AFFILIATIONS | University of St Andrews |
| ORCID | 0000-0002-1845-6829 |
| VERIFIED | Yes |
| TOTAL WORKS | 5 |
| TOTAL CITATIONS | 1 |
| WORKS AS AUTHOR | 5 |
| WORKS AS EDITOR | 0 |
| FIRST PUBLICATION YEAR | 2000 |
| LATEST PUBLICATION YEAR | 2017 |
| H-INDEX | 1 |
Hybrid Grammars for Parsing of Discontinuous Phrase Structures and Non-Projective Dependency Structures
We explore the concept of hybrid grammars, which formalize and generalize a range of existing frameworks for dealing with discontinuous syntactic structures. Covered are both discontinuous phrase structures and non-projective dependency structures. Technically, hybrid grammars are related to synchronous grammars, where one grammar component generates linear structures and another generates hierarchical structures. By coupling lexical elements of …
Splittability of Bilexical Context-Free Grammars is Undecidable
Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(∣w∣ 4 ), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotical…
A General Technique to Train Language Models on Language Models
We show that under certain conditions, a language model can be trained on the basis of a second language model. The main instance of the technique trains a finite automaton on the basis of a probabilistic context-free grammar, such that the Kullback-Leibler distance between grammar and trained automaton is provably minimal. This is a substantial generalization of an existing algorithm to train an n-gram model on the basis of a probabilistic conte…
Weighted Deductive Parsing and Knuth's Algorithm
We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system
Practical Experiments with Regular Approximation of Context-Free Languages
Several methods are discussed that construct a finite automaton given a context-free grammar, including both methods that lead to subsets and those that lead to supersets of the original context-free language. Some of these methods of regular approximation are new, and some others are presented here in a more refined form with respect to existing literature. Practical experiments with the different methods of regular approximation are performed f…
Weighted Deductive Parsing and Knuth's Algorithm
We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system
Practical Experiments with Regular Approximation of Context-Free Languages
Several methods are discussed that construct a finite automaton given a context-free grammar, including both methods that lead to subsets and those that lead to supersets of the original context-free language. Some of these methods of regular approximation are new, and some others are presented here in a more refined form with respect to existing literature. Practical experiments with the different methods of regular approximation are performed f…
Weighted Deductive Parsing and Knuth's Algorithm
We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system
A General Technique to Train Language Models on Language Models
We show that under certain conditions, a language model can be trained on the basis of a second language model. The main instance of the technique trains a finite automaton on the basis of a probabilistic context-free grammar, such that the Kullback-Leibler distance between grammar and trained automaton is provably minimal. This is a substantial generalization of an existing algorithm to train an n-gram model on the basis of a probabilistic conte…
Splittability of Bilexical Context-Free Grammars is Undecidable
Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(∣w∣ 4 ), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotical…
Hybrid Grammars for Parsing of Discontinuous Phrase Structures and Non-Projective Dependency Structures
We explore the concept of hybrid grammars, which formalize and generalize a range of existing frameworks for dealing with discontinuous syntactic structures. Covered are both discontinuous phrase structures and non-projective dependency structures. Technically, hybrid grammars are related to synchronous grammars, where one grammar component generates linear structures and another generates hierarchical structures. By coupling lexical elements of …
Artificial Intelligence (5 works) · Computer Science (5 works) · Context-free grammar (4 works) · Natural language processing (4 works) · Parsing (4 works) · Programming language (4 works) · Rule-based machine translation (4 works) · Context (archaeology (3 works) · Grammar (3 works) · Linguistics (3 works)