Page 1

Displaying 1 – 7 of 7

Showing per page

Labeled shortest paths in digraphs with negative and positive edge weights

Phillip G. Bradford, David A. Thomas (2009)

RAIRO - Theoretical Informatics and Applications

This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...

Learning discrete categorial grammars from structures

Jérôme Besombes, Jean-Yves Marion (2008)

RAIRO - Theoretical Informatics and Applications

We define the class of discrete classical categorial grammars, similar in the spirit to the notion of reversible class of languages introduced by Angluin and Sakakibara. We show that the class of discrete classical categorial grammars is identifiable from positive structured examples. For this, we provide an original algorithm, which runs in quadratic time in the size of the examples. This work extends the previous results of Kanazawa. Indeed, in our work, several types can be associated to a word...

Currently displaying 1 – 7 of 7

Page 1