Author name cluster

Mark-Jan Nederhof

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 2021 Journal Article

A derivational model of discontinuous parsing

Mark-Jan Nederhof
Anssi Yli-Jyrä

The notion of latent-variable probabilistic context-free derivation of syntactic structures is enhanced to allow heads and unrestricted discontinuities. The chosen formalization covers both constituency parsing and dependency parsing. By the new framework, one obtains a probability distribution over the space of all discontinuous parses. This lends itself to intrinsic evaluation in terms of cross-entropy. The derivational model is accompanied by an equivalent automaton model, which can be used for deterministic parsing.

Details DOI

TCS Journal 2008 Journal Article

Computation of distances for regular and context-free probabilistic languages

Mark-Jan Nederhof
Giorgio Satta

Several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. In most cases, only pairs of probabilistic regular languages were considered. In this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.

Details DOI

I&C Journal 2004 Journal Article

The language intersection problem for non-recursive context-free grammars

Mark-Jan Nederhof
Giorgio Satta

We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive.

Details DOI